今天再看藍(lán)橋杯的時(shí)候，看見(jiàn)一道有趣的貪心題。

問(wèn)題描述
　　小明先把硬幣擺成了一個(gè) n 行 m 列的矩陣。

　　隨后，小明對(duì)每一個(gè)硬幣分別進(jìn)行一次 Q 操作。

　　對(duì)第x行第y列的硬幣進(jìn)行 Q 操作的定義：將所有第 i*x 行，第 j*y 列的硬幣進(jìn)行翻轉(zhuǎn)。

　　其中i和j為任意使操作可行的正整數(shù)，行號(hào)和列號(hào)都是從1開(kāi)始。

　　當(dāng)小明對(duì)所有硬幣都進(jìn)行了一次 Q 操作后，他發(fā)現(xiàn)了一個(gè)奇跡——所有硬幣均為正面朝上。

　　小明想知道最開(kāi)始有多少枚硬幣是反面朝上的。于是，他向他的好朋友小M尋求幫助。

　　聰明的小M告訴小明，只需要對(duì)所有硬幣再進(jìn)行一次Q操作，即可恢復(fù)到最開(kāi)始的狀態(tài)。然而小明很懶，不愿意照做。于是小明希望你給出他更好的方法。幫他計(jì)算出答案。
輸入格式
　　輸入數(shù)據(jù)包含一行，兩個(gè)正整數(shù) n m，含義見(jiàn)題目描述。
輸出格式
　　輸出一個(gè)正整數(shù)，表示最開(kāi)始有多少枚硬幣是反面朝上的。
樣例輸入
2 3
樣例輸出
1
數(shù)據(jù)規(guī)模和約定
　　對(duì)于10%的數(shù)據(jù)，n、m <= 10^3；
　　對(duì)于20%的數(shù)據(jù)，n、m <= 10^7；
　　對(duì)于40%的數(shù)據(jù)，n、m <= 10^15；
　　對(duì)于10%的數(shù)據(jù)，n、m <= 10^1000（10的1000次方）。

可以知道，假設(shè)是一個(gè)（1，m）的矩陣，那么某個(gè)硬幣被翻的次數(shù)是由它所在的位置決定的，假設(shè)一個(gè)硬幣位置為（1，6）那么，在翻（1，1），（1，2），（1，3）時(shí)都會(huì)被翻一次，加上其自身，翻到的次數(shù)就是四次；最后狀態(tài)不變。如果一個(gè)硬幣的位置是（1，5），那么翻（1，1），（1，5）的時(shí)候被翻轉(zhuǎn)；結(jié)果狀態(tài)不變。如果是（1，9），那么（1，1），（1，3），（1，9）時(shí)翻轉(zhuǎn)，狀態(tài)改變。相同，如果是（1，4），狀態(tài)也會(huì)改變，其原因就是該數(shù)的兩個(gè)約數(shù)相等，所以減少了一次翻轉(zhuǎn)的機(jī)會(huì)。所以對(duì)于這個(gè)行數(shù)為1的矩陣，狀態(tài)被改變的數(shù)目也就是在m以內(nèi)所有可開(kāi)方數(shù)的數(shù)目和，我們只要知道m(xù)以內(nèi)有多少個(gè)數(shù)可以寫(xiě)成m=k^2的方式即可。
我們假設(shè)m=30，那么最大的看開(kāi)方數(shù)是5（5^2=25），所以，就必定存在4，3，2，1四個(gè)可開(kāi)方數(shù)，結(jié)合上面的推論，有5個(gè)硬幣的狀態(tài)被改變，最初共有5個(gè)反面的硬幣。
在我們計(jì)算的時(shí)候，只需要求出一個(gè)數(shù)的最大可開(kāi)方數(shù)取整，即是可開(kāi)方數(shù)的個(gè)數(shù)。

將范圍擴(kuò)大到（n，m），這時(shí)要考慮的是行數(shù)增加的影響，若位置是（2，9），該硬幣不但會(huì)在（2，1），（2，3），（2，9）時(shí)被翻轉(zhuǎn)三次，還會(huì)在（1，1），（1，3），（1，9）時(shí)被翻轉(zhuǎn)，故在行，列，位置都是不可開(kāi)方數(shù)的時(shí)候才會(huì)出現(xiàn)狀態(tài)改變，設(shè)n，m的可開(kāi)方數(shù)目分別為i，j，那么該矩陣的總反面硬幣個(gè)數(shù)為i與j的積。

因此我們的計(jì)算方法為：
1，尋找兩個(gè)數(shù)的最大可開(kāi)方數(shù)
2，將最大可開(kāi)方數(shù)相乘

具體實(shí)現(xiàn)涉及到了大數(shù)的計(jì)算，字符串的應(yīng)用問(wèn)題，在這里就不多說(shuō)了。具體代碼演示：

#include <iostream>
#include <string>
#include <string.h>
#include <sstream>
using namespace std;


string multiply(string str1,string str2)//字符串相乘函數(shù) 
{
string str="";  //最終結(jié)果 
int len1=str1.size(),len2=str2.size(),i,j;//計(jì)算兩個(gè)字符串的函數(shù) 
int result[1000]={0};  //開(kāi)辟數(shù)組存乘積并初始化 
for(i=len1-1;i>=0;i--)
 for(j=len2-1;j>=0;j--)
 {
  result[i+j+1]+=(str1[i]-'0')*(str2[j]-'0');
 }
for(i=len1+len2-1;i>=1;i--)//讓數(shù)組的每一位都是正確的數(shù) 
{
result[i-1]=result[i-1]+result[i]/10;
result[i]=result[i]%10;
}
for(i=0;result[i]==0;i++) //前導(dǎo)零不要 
    ;
    for(j=i;j<len1+len2;j++)//轉(zhuǎn)成字符串形式 
        str+=result[j]+'0';
    return str;
}
int compare(string str1,string str,int pos)//字符串比較函數(shù) 
{
    int len1=str1.size();
    int len2=str.size();
    if(len2>len1+pos)return 0;
    if(len2<len1+pos)return 1;
    for(int i=0;i<len2;i++)
    {
    if(str1[i]-'0'>str[i]-'0')return 1;
    if(str1[i]-'0'<str[i]-'0')return 0;
}
}


string strsqrt(string str)//對(duì)字符串開(kāi)方取整函數(shù) 
{
int len=str.size();
string str1="",str2="";
for(int i=0;i<(len+1)/2;i++)//若len為偶數(shù)，len/2=(len+1)/2;若len為奇數(shù)，len/2+1=(len+1)/2 
       for(int j=0;j<=9;j++)   //因?yàn)槊恳晃坏臄?shù)值都是0~9 
       {
         str1=str2;
          str1+=j+'0';
         if(compare(multiply(str1,str1),str,2*((len+1)/2-1-i))==1)//由于str1后少了(len+1)/2-i-1個(gè)0，所以平方以后少了2*((len+1)/2-i-1)個(gè)  
            {
               str2+=j-1+'0';
              break;
            }
         if(j==9)
           str2+='9';
       }
    return str2;
}


int main()
{
string n,m;
cin>>n>>m;
cout<<multiply(strsqrt(n),strsqrt(m))<<endl;
return 0;
}