c/c++算法问题 矩阵翻硬币

c/c++算法问题 矩阵翻硬币
问题描述
　　小明先把硬币摆成了一个 n 行 m 列的矩阵。
　　随后，小明对每一个硬币分别进行一次 Q 操作。
　　对第x行第y列的硬币进行 Q 操作的定义：将所有第 i*x 行，第 j*y 列的硬币进行翻转。
　　其中i和j为任意使操作可行的正整数，行号和列号都是从1开始。
　　当小明对所有硬币都进行了一次 Q 操作后，他发现了一个奇迹——所有硬币均为正面朝上。
　　小明想知道最开始有多少枚硬币是反面朝上的。于是，他向他的好朋友小M寻求帮助。
　　聪明的小M告诉小明，只需要对所有硬币再进行一次Q操作，即可恢复到最开始的状态。然而小明很懒，不愿意照做。于是小明希望你给出他更好的方法。帮他计算出答案。
输入格式
　　输入数据包含一行，两个正整数 n m，含义见题目描述。
输出格式
　　输出一个正整数，表示最开始有多少枚硬币是反面朝上的。
样例输入
2 3
样例输出
1
数据规模和约定
　　对于10%的数据，n、m

#include<iostream>
#include<cmath>

#define M 10000
#define N 10000

using namespace std;

bool a[M][N];

void init(int m,int n)
{
     int i,j;
     for(i=1;i<=m;i++){
         for(j=1;j<=n;j++){
             a[i][j]=true;
         }
     }

}
void qTurn (int m,int n)
{
    int x;
    int y;
    int i;
    int j;
    for (x =1; x<=m;x++ ){
        for (y = 1; y<=n; y++ ){
            for ( i=1; i<=m/ x;i++ ){
                for (j=1; j<=n/y;j++ ){
                        a[i* x][j * y] =  !a[i* x][j * y];
                }
            }
        }
    }
}
int sum(int m,int n){
    int i,j;
    int sum;
    sum=0;
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            if(!a[i][j]) sum ++;
        }
    }
    return sum;
} 
int main(){
   int m,n;
   while(cin >> m){
       cin >> n;
       init(m,n);
       qTurn(m,n);
       cout << sum(m,n)<<endl;    
   }
}这是模拟操作的做法，并不能保证所有的数据都正确，因为m，n很大的时候，数组太大。楼下的是正解。只有坐标为(i, j)，i和j都是完全平方数的硬币是才会被翻面，其他的硬币都会维持正面。
因为如果不是完全平方数的话有偶数个约数，会被翻转偶数次。而完全平方数有奇数个约数，比如4，有1,2,4三个约数，会被翻奇数次，反面的变为正面。初始反面的有sqrt(n) * sqrt(m)个。
再举个例子吧，比如a[2][4],此时2有2个约数1,2,4有3个约数1,2,4。它将被反转2*3=6次。只有奇数*奇数才是奇数，所以只有i和j都是完全平方数时，才会被翻面。#include<iostream>
#include<cmath>
using namespace std;

int main(){
    unsigned long long m,n;
    while(cin >> m){
        cin >> n;
        cout << (int)sqrt(m)*(int)sqrt(n)<<endl;
    }
    return 0; 
}