## 矩阵翻硬币 ~~~ 问题描述 　　小明先把硬币摆成了一个 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次方）。 ~~~ 算法分析： 1.求每个位置的硬币的翻转次数，奇数代表反面，偶数代表正面。 2.设某个位置为(x,y),执行Q操作后，所有（x*i,y*j）都要翻转。可以推出，使（x，y）翻转的位置（a，b）必须满足a是x的因子，b是y的因子。所以是（x，y）反转的次数就是x和y的因子数之积。 3.问题就在于两个数的因子数之积什么为奇数？我们知道只有奇数相乘结果才为奇数，因为因子总是成对出现的，所以只有有两个因子相等才会出现这种结果。也就是说只有两个数同时可以开平方根时，这个位置才是反面。 4.剩下就要求在n*m找出多少对可开方的数。于是得出：f(n,m)=√n*√m 5.由于数据比较大，所以要用特定的算法来计算。 源码： import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); String n=in.next(); String m=in.next(); BigInteger nb=new BigInteger(n); BigInteger mb=new BigInteger(m); BigInteger res=sqrt(nb).multiply(sqrt(mb)); System.out.println(res.toString()); } public static BigInteger sqrt(BigInteger num){ BigInteger two=new BigInteger("2"); BigInteger num1=BigInteger.ONE; BigInteger num2=num.divide(num1); BigInteger center,temp; while(num1.compareTo(num2)!=0){ center=(num1.add(num2)).divide(two); temp=num.divide(center); if(temp.compareTo(center)<0){ //num2=center.subtract(BigInteger.ONE); if(temp.compareTo(num1)<=0&&center.compareTo(num2)>=0){ break; } num1=temp; num2=center; }else if(temp.compareTo(center)>0){ //num1=center.add(BigInteger.ONE); if(temp.compareTo(num2)>=0&&center.compareTo(num1)<=0){ break; } num1=center; num2=temp; }else{ num1=center; num2=center; } } return num1; } }