今天再看藍橋杯的時候铣墨，看見一道有趣的貪心題。
問題描述
小明先把硬幣擺成了一個 n 行 m 列的矩陣办绝。
隨后踏兜，小明對每一個硬幣分別進行一次 Q 操作。
對第x行第y列的硬幣進行 Q 操作的定義：將所有第 i*x 行八秃，第 j*y 列的硬幣進行翻轉。
其中i和j為任意使操作可行的正整數(shù)肉盹，行號和列號都是從1開始昔驱。
當小明對所有硬幣都進行了一次 Q 操作后，他發(fā)現(xiàn)了一個奇跡——所有硬幣均為正面朝上上忍。
小明想知道最開始有多少枚硬幣是反面朝上的骤肛。于是纳本，他向他的好朋友小M尋求幫助。
聰明的小M告訴小明腋颠，只需要對所有硬幣再進行一次Q操作繁成，即可恢復到最開始的狀態(tài)。然而小明很懶淑玫，不愿意照做巾腕。于是小明希望你給出他更好的方法。幫他計算出答案絮蒿。
輸入格式
輸入數(shù)據(jù)包含一行尊搬，兩個正整數(shù) n m，含義見題目描述土涝。
輸出格式
輸出一個正整數(shù)佛寿，表示最開始有多少枚硬幣是反面朝上的。
樣例輸入
2 3
樣例輸出
1
數(shù)據(jù)規(guī)模和約定
對于10%的數(shù)據(jù)但壮，n冀泻、m <= 10^3；
對于20%的數(shù)據(jù)蜡饵，n弹渔、m <= 10^7；
對于40%的數(shù)據(jù)验残，n捞附、m <= 10^15；
對于10%的數(shù)據(jù)您没，n鸟召、m <= 10^1000（10的1000次方）。
可以知道氨鹏，假設是一個（1欧募，m）的矩陣，那么某個硬幣被翻的次數(shù)是由它所在的位置決定的仆抵，假設一個硬幣位置為（1跟继，6）那么，在翻（1镣丑，1）舔糖，（1，2）莺匠，（1金吗，3）時都會被翻一次，加上其自身，翻到的次數(shù)就是四次摇庙；最后狀態(tài)不變旱物。如果一個硬幣的位置是（1，5）卫袒，那么翻（1宵呛，1），（1夕凝，5）的時候被翻轉宝穗；結果狀態(tài)不變。如果是（1迹冤，9）讽营，那么（1，1）泡徙，（1橱鹏，3），（1堪藐，9）時翻轉莉兰，狀態(tài)改變。相同礁竞，如果是（1糖荒，4），狀態(tài)也會改變模捂，其原因就是該數(shù)的兩個約數(shù)相等捶朵，所以減少了一次翻轉的機會。所以對于這個行數(shù)為1的矩陣狂男，狀態(tài)被改變的數(shù)目也就是在m以內所有可開方數(shù)的數(shù)目和综看，我們只要知道m(xù)以內有多少個數(shù)可以寫成m=k^2的方式即可。
我們假設m=30岖食，那么最大的看開方數(shù)是5（5^2=25）红碑，所以，就必定存在4泡垃，3析珊，2，1四個可開方數(shù)蔑穴，結合上面的推論忠寻，有5個硬幣的狀態(tài)被改變，最初共有5個反面的硬幣存和。
在我們計算的時候锡溯，只需要求出一個數(shù)的最大可開方數(shù)取整赶舆，即是可開方數(shù)的個數(shù)。
將范圍擴大到（n祭饭，m），這時要考慮的是行數(shù)增加的影響叙量，若位置是（2倡蝙，9）绞佩，該硬幣不但會在（2寺鸥，1），（2品山，3）胆建，（2，9）時被翻轉三次肘交，還會在（1笆载，1），（1涯呻，3）凉驻，（1，9）時被翻轉复罐，故在行涝登，列，位置都是不可開方數(shù)的時候才會出現(xiàn)狀態(tài)改變效诅，設n胀滚，m的可開方數(shù)目分別為i，j乱投，那么該矩陣的總反面硬幣個數(shù)為i與j的積咽笼。
因此我們的計算方法為：
1，尋找兩個數(shù)的最大可開方數(shù)
2篡腌，將最大可開方數(shù)相乘
具體實現(xiàn)涉及到了大數(shù)的計算褐荷，字符串的應用問題，在這里就不多說了嘹悼。具體代碼演示：
#include <iostream>
#include <string>
#include <string.h>
#include <sstream>
using namespace std;
string multiply(string str1,string str2)//字符串相乘函數(shù)
{
string str=""; //最終結果
int len1=str1.size(),len2=str2.size(),i,j;//計算兩個字符串的函數(shù)
int result[1000]={0}; //開辟數(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++) //前導零不要
;
for(j=i;j<len1+len2;j++)//轉成字符串形式
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)//對字符串開方取整函數(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++) //因為每一位的數(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個0杨伙，所以平方以后少了2*((len+1)/2-i-1)個
{
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;
}
