藍橋杯：矩陣翻硬幣

題目地址：http://lx.lanqiao.org/problem.page?gpid=T126

這道題強烈建議用java做，畢竟自帶BigInteger類。

此題看似是一道模擬題，但由于數據規模很大（10的1000次方），只能找規律。規律是最終結果為sqrt(n)*sqrt(m)，然后此題就成了大數開根的題。

做法是先對數字的長度進行判斷，如果被開根的數是偶數位的（例如4365，4位），開根后就為其原位數的一半（66，2位）。如果其位數是奇數位的（例如121，3位），開根后其位數就是原位數的二分之一向下區整再加一（11，3/2+1=2位）。

確定了位數之后就對其進行由高位至低位，由小到大的遍歷。

以4356為例，先確定答案是兩位的，初始化為00，從十位開始1-9的遍歷，到70的時候該數的平方為4900>4356，從而確定十位是7-1=6。個位同理。

本程序有多次char[], String, BigIntger之間的轉化，要正確轉化。

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
           Scanner cin = new Scanner(System.in); 
           String s1 = cin.next();
           String s2 = cin.next();
           BigInteger ans1 = BigSqrt(s1);
           BigInteger ans2 = BigSqrt(s2);
           //System.out.println(ans1+" "+ans2);
           BigInteger ans = ans1.multiply(ans2);
           System.out.println(ans);
    }

    private static BigInteger BigSqrt(String s) {        
        int mlen = s.length();    //被開方數的長度
        int len;    //開方后的長度
        BigInteger beSqrtNum = new BigInteger(s);//被開方數
        BigInteger sqrtOfNum;    //存儲開方后的數
        BigInteger sqrtOfNumMul;    //開方數的平方
        String sString;//存儲sArray轉化后的字符串
        if(mlen%2 == 0)    len = mlen/2;
        else    len = mlen/2+1;
        char[] sArray = new char[len];
        Arrays.fill(sArray, '0');//開方數初始化為0
        for(int pos=0; pos<len; pos++){
            //從最高開始遍歷數組，每一位都轉化為開方數平方后剛好不大于被開方數的程度
            for(char num='1'; num<='9'; num++){
                sArray[pos] = num;
                sString = String.valueOf(sArray);
                sqrtOfNum = new BigInteger(sString);
                sqrtOfNumMul = sqrtOfNum.multiply(sqrtOfNum);
                if(sqrtOfNumMul.compareTo(beSqrtNum) == 1){
                    sArray[pos]-=1;
                    break;    
                }    
            }
        }
        return new BigInteger(String.valueOf(sArray));
    }
}

?