PREV-34矩阵翻硬币 （高精度开方，相乘）

问题描述 　　小明先把硬币摆成了一个 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 <= 10^3； 　　对于20%的数据，n、m <= 10^7； 　　对于40%的数据，n、m <= 10^15； 　　对于10%的数据，n、m <= 10^1000（10的1000次方）。

此题经过思考和验证之后就会发现一个规律，就是当硬币在位置（X,Y）时，如果 X的约数个数乘以 Y的约数个数，结果为奇数，则可证明此坐标上的硬币为刚开始为反的硬币，而结果为偶数的坐标则不符合。

证明：

证明其实很简单，例如(2,4)坐标，我们一一可求出来可由（1，1），（1,2），（1,4），（2,1），（2,2）（2，4）这6个位置翻转一次（2,4）位置的硬币，翻转次数为6次。

而2的约数为 1，2。  共2个。

4的约数为1,2,4。       共3个。

所以根据全排列可知 （2,4）的约数坐标有2*3个。

由题意可知如果翻转次数为偶数次，则刚开始为正面向上；为奇数，则刚开始为反面向上。所以我们只要求出坐标（1~X，1~Y）中有多少符合即可。

相乘为奇数则说明X和Y的约数个数都为奇数个才成立，由此说明只有1^2,2^2,3^2,,,,,,n^2这样的数才符合。所以1~X里有多少个，结果就是sqrt（X）个嘛、

所以结果就等于sqrt（X）*sqrt（Y）。但是因为数据太大，需要高精度开方函数。

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> //#include <stack> //#include <map> //#include <set> //#include <vector> //#include <queue> //#define mem(p,k) memset(p,k,sizeof(p)); //#define lson l,m,rt<<1 //#define rson m+1,r,rt<<1|1 //#define inf 0x6fffffff //#define LL long long using namespace std; string Mul(string a,string b){//大数相乘 int c[2010]={0}; string ans=""; //fill(c.begin(),c.begin()+2000,0); int lena=a.length(),lenb=b.length(),len; for(int i=0;i<lena;i++){ for(int j=0;j<lenb;j++){ c[lena-1-i+lenb-1-j]+=(a[i]-48)*(b[j]-48); } } len=lena+lenb; for(int i=0;i<len;i++){ c[i+1]+=c[i]/10; c[i]%=10; //cout<<c[i]<<" "; } if(!c[len-1])len--; for(int i=len-1;i>=0;i--)ans+=c[i]+48; return ans; } int cmp(string a,string b){ int lena=a.length(); if(a.length()==b.length()){ for(int i=0;i<lena;i++){ if(a[i]!=b[i]){ return a[i]>b[i]?1:-1; } } return 0; } return a.length()>b.length()?1:-1; } string Bigsqrt(string a){//高精度开方 int len=(a.length()+1)>>1; string c="1"; for(int i=1;i<len;i++)c+='0'; for(int i=0;i<len;i++){ while(cmp(Mul(c,c),a)<1){ c[i]++; if(c[i]==58)break; } c[i]--; } return c; } int main() { string n,m; cin>>n>>m; int lenn=n.length(),lenm=m.length(); //cout<<mul(n,m); //cout<<Bigsqrt(n); cout<<Mul(Bigsqrt(n),Bigsqrt(m))<<endl; return 0; }