## 矩陣翻硬幣 ~~~ 問題描述 　　小明先把硬幣擺成了一個 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; } }