問(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開始。

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

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

　　聰明的小M告訴小明，只需要對(duì)所有硬幣再進(jìn)行一次Q操作，即可恢復(fù)到最開始的狀態(tài)。然而小明很懶，不愿意照做。于是小明希望你給出他更好的方法。幫他計(jì)算出答案。 輸入格式 　　輸入數(shù)據(jù)包含一行，兩個(gè)正整數(shù) n m，含義見題目描述。 輸出格式 　　輸出一個(gè)正整數(shù)，表示最開始有多少枚硬幣是反面朝上的。 樣例輸入 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次方）。 本來(lái)以為還是一道模擬題，聰（bai）明（chi）的小M也是too young too simple，其實(shí)，看到題目的數(shù)據(jù)范圍我們應(yīng)該已經(jīng)感覺到，模擬絕對(duì)沒戲，接下來(lái)我們仔細(xì)分析一下這道題的解法。

1.很容易得出，如果一枚硬幣被翻了奇數(shù)次，那么它原來(lái)的狀態(tài)肯定是反面朝上，所以，我們要找的就是被翻了奇數(shù)次的硬幣

3.對(duì)于一個(gè)硬幣，我們必須同時(shí)考慮其橫坐標(biāo)x和縱坐標(biāo)y，假如橫坐標(biāo)被翻了a次，縱坐標(biāo)被翻了b次，則這個(gè)硬幣總共被翻了a*b次，若想要這個(gè)硬幣被翻奇數(shù)次，a和b必須都得是奇數(shù)，即x和y都有奇數(shù)個(gè)約數(shù)

4.那么問(wèn)題來(lái)了：哪些數(shù)有奇數(shù)個(gè)約數(shù)呢？不管你知不知道，反正現(xiàn)在你知道了，完全平方數(shù)有奇數(shù)個(gè)約數(shù)。那么什么又是完全平方數(shù)呢，簡(jiǎn)單的說(shuō)就是n^2，n為自然數(shù)，也就是0，1，4，9……

5.問(wèn)題又來(lái)了，怎么求完全平方數(shù)的個(gè)數(shù)呢，首先，我們已經(jīng)知道了這個(gè)矩陣式n*m的，而且是從1開始編號(hào)的，對(duì)于n，我們可以求sqrt（n），然后取整，容易想出，在1-n的范圍內(nèi)的完全平方數(shù)的個(gè)數(shù)為（int）（sqrt（n））個(gè)，而sqrt（n）*sqrt（m）就是所有的橫縱坐標(biāo)都是完全平方數(shù)的硬幣的個(gè)數(shù)。

6.下面，我們迎來(lái)了終極問(wèn)題，題目思路有了，但是超大規(guī)模的數(shù)據(jù)問(wèn)題并沒有得到解決，反而更麻煩了，因?yàn)榫尤贿€搞出了個(gè)開方的操作，但很不幸，這就是一道悲催的大數(shù)高精度題，而且還得自己寫出大數(shù)相乘，大數(shù)開方，大數(shù)比較等操作

OK，下面開始就全部都是大數(shù)運(yùn)算的相關(guān)知識(shí)了，如果你已經(jīng)很熟悉可以無(wú)視

首先，讓我們明確一下思路，到底如何實(shí)現(xiàn)乘法和開方，對(duì)于大數(shù)的存儲(chǔ)，我們使用string，因?yàn)樗拈L(zhǎng)度比較容易控制

乘法：其實(shí)有很多速度快而且更巧妙的大數(shù)乘法，但是在藍(lán)橋杯，我們只要使用模擬手算法應(yīng)該是問(wèn)過(guò)，雖說(shuō)是模擬，但也有一些我們常用但不太了解的規(guī)律，我們?cè)谑炙愠朔ǖ臅r(shí)候，需要進(jìn)行移位和進(jìn)位，這兩個(gè)操作我們會(huì)通過(guò)兩步完成

1.移位：對(duì)于兩個(gè)數(shù)a=12，b=25，在相乘的時(shí)候我們讓每一位數(shù)分別相乘，即a[0]*b[0]=2 , a[0]*b[1]=5 , a[1]*b[0]=4 , a[1]*b[1]=10，那么規(guī)律就是，對(duì)于兩個(gè)數(shù)a[i] , b[j]，所有i+j相同的數(shù)都要加到一起，所以我們要把5+4=9合并為一個(gè)數(shù)，也就是說(shuō)，將每一位數(shù)相乘之后，我們實(shí)際得到了2，9，10三個(gè)沒有進(jìn)位的數(shù)

2.進(jìn)位：通過(guò)上面的操作，我們的2，9，10三個(gè)沒有進(jìn)位的數(shù)，下面就要進(jìn)行進(jìn)位，因?yàn)槲覀兪前迅呶幌喑说玫降臄?shù)放在前面，地位相乘得到的數(shù)放在后面，所以這三個(gè)數(shù)排列自然也是高位在前，地位在后，所以要從右向左進(jìn)位，進(jìn)位的方法就是a[i]=a[i+1]/10 , a[i+1]=a[i+1]%10，如果放到這三個(gè)數(shù)上面，就是，9+10/10=10，然后10%10=0，這三個(gè)數(shù)變成2，10，0，再一次就是2+10/10=3，10%10=0，三個(gè)數(shù)變?yōu)?，0，0，而這正是我們要求的結(jié)果，在實(shí)際操作中，我們習(xí)慣于將數(shù)倒著存放，即將數(shù)存為10，9，2，這是為了進(jìn)位方便，因?yàn)槿绻虻脑捜绻罡呶话l(fā)生進(jìn)位我們就要將每一個(gè)數(shù)向后移動(dòng)一位從而挪出一個(gè)空位，想想都麻煩，倒序的話因?yàn)槭窍蚝筮M(jìn)位，想怎么進(jìn)就怎么進(jìn)

開方：這個(gè)開方方法不是我想出來(lái)的，是參照了網(wǎng)上的一個(gè)方法，我感覺挺好。實(shí)際上也可以用牛頓逼近法。

這個(gè)方法的前提：假如一個(gè)數(shù)有偶數(shù)位n，那么這個(gè)數(shù)的方根有n/2位；如果n為奇數(shù)，那么方根為（n+1）/2位。

然后，讓我們實(shí)際看一個(gè)例子，我們假設(shè)這個(gè)數(shù)就是1200

1.很明顯，它有4位，所以它的方根有2位，然后，我們通過(guò)下面的方法來(lái)枚舉出它的整數(shù)根

00*00=0<1200

所以，這個(gè)根的十位就是3，然后，再枚舉個(gè)位

32*32=1024<1200

33*33=1089<1200

34*34=1156<1200

35*35=1225>1200

所以，這個(gè)根就是34，因?yàn)槠椒皆鲩L(zhǎng)的速度還是比較快的，所以速度沒有太大問(wèn)題，這里有一個(gè)地方需要處理一下，如果一個(gè)數(shù)很長(zhǎng)，那么它的方根的位數(shù)也比較長(zhǎng)，在枚舉高位的時(shí)候，我們沒有必要把后面的0都加上，因?yàn)槟菢訒?huì)影響速度，其實(shí)0的個(gè)數(shù)完全可以算出來(lái)，然后將0的個(gè)數(shù)一起送入比較函數(shù)比較即可，這樣可以提高速度

比較：上面我們說(shuō)過(guò)，比較函數(shù)接受的兩個(gè)數(shù)只有一個(gè)是完整的數(shù)，另外一個(gè)實(shí)際上是高幾位的平方和0的個(gè)數(shù)，但處理方式差不多，都是先比較位數(shù)，位數(shù)大數(shù)就大，位數(shù)一樣就逐位比較，只要?jiǎng)e忘了比較那一堆0就好了，最后其實(shí)不用把情況分的太清楚，只要返回0，1就行，因?yàn)橹挥挟?dāng)一個(gè)數(shù)大于n的時(shí)候才對(duì)我們有意義