問題描述 小明先把硬幣擺成了一個 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次方）。 本來以為還是一道模擬題，聰（bai）明（chi）的小M也是too young too simple，其實，看到題目的數據范圍我們應該已經感覺到，模擬絕對沒戲，接下來我們仔細分析一下這道題的解法。
1.很容易得出，如果一枚硬幣被翻了奇數次，那么它原來的狀態肯定是反面朝上，所以，我們要找的就是被翻了奇數次的硬幣
Q 操作的定義：將所有第 i*x 行，第 j*y 列的硬幣進行翻轉。正向看可能不好想，那么我們反向看一下，對于一個橫坐標為N的硬幣，在翻哪些硬幣（橫坐標x）的時候會翻到它呢？其實就是這個數N所有的約數，比如橫坐標為4的硬幣，那么，在翻橫坐標為1，2，4的硬幣時都會翻到它，縱坐標的情況是一樣的。3.對于一個硬幣，我們必須同時考慮其橫坐標x和縱坐標y，假如橫坐標被翻了a次，縱坐標被翻了b次，則這個硬幣總共被翻了a*b次，若想要這個硬幣被翻奇數次，a和b必須都得是奇數，即x和y都有奇數個約數
4.那么問題來了：哪些數有奇數個約數呢？不管你知不知道，反正現在你知道了，完全平方數有奇數個約數。那么什么又是完全平方數呢，簡單的說就是n^2，n為自然數，也就是0，1，4，9……
5.問題又來了，怎么求完全平方數的個數呢，首先，我們已經知道了這個矩陣式n*m的，而且是從1開始編號的，對于n，我們可以求sqrt（n），然后取整，容易想出，在1-n的范圍內的完全平方數的個數為（int）（sqrt（n））個，而sqrt（n）*sqrt（m）就是所有的橫縱坐標都是完全平方數的硬幣的個數。
6.下面，我們迎來了終極問題，題目思路有了，但是超大規模的數據問題并沒有得到解決，反而更麻煩了，因為居然還搞出了個開方的操作，但很不幸，這就是一道悲催的大數高精度題，而且還得自己寫出大數相乘，大數開方，大數比較等操作
OK，下面開始就全部都是大數運算的相關知識了，如果你已經很熟悉可以無視
首先，讓我們明確一下思路，到底如何實現乘法和開方，對于大數的存儲，我們使用string，因為它的長度比較容易控制
乘法：其實有很多速度快而且更巧妙的大數乘法，但是在藍橋杯，我們只要使用模擬手算法應該是問過，雖說是模擬，但也有一些我們常用但不太了解的規律，我們在手算乘法的時候，需要進行移位和進位，這兩個操作我們會通過兩步完成
1.移位：對于兩個數a=12，b=25，在相乘的時候我們讓每一位數分別相乘，即a[0]*b[0]=2 , a[0]*b[1]=5 , a[1]*b[0]=4 , a[1]*b[1]=10，那么規律就是，對于兩個數a[i] , b[j]，所有i+j相同的數都要加到一起，所以我們要把5+4=9合并為一個數，也就是說，將每一位數相乘之后，我們實際得到了2，9，10三個沒有進位的數
2.進位：通過上面的操作，我們的2，9，10三個沒有進位的數，下面就要進行進位，因為我們是把高位相乘得到的數放在前面，地位相乘得到的數放在后面，所以這三個數排列自然也是高位在前，地位在后，所以要從右向左進位，進位的方法就是a[i]=a[i+1]/10 , a[i+1]=a[i+1]%10，如果放到這三個數上面，就是，9+10/10=10，然后10%10=0，這三個數變成2，10，0，再一次就是2+10/10=3，10%10=0，三個數變為3，0，0，而這正是我們要求的結果，在實際操作中，我們習慣于將數倒著存放，即將數存為10，9，2，這是為了進位方便，因為如果正序的話如果最高位發生進位我們就要將每一個數向后移動一位從而挪出一個空位，想想都麻煩，倒序的話因為是向后進位，想怎么進就怎么進
開方：這個開方方法不是我想出來的，是參照了網上的一個方法，我感覺挺好。實際上也可以用牛頓逼近法。
這個方法的前提：假如一個數有偶數位n，那么這個數的方根有n/2位；如果n為奇數，那么方根為（n+1）/2位。
然后，讓我們實際看一個例子，我們假設這個數就是1200
1.很明顯，它有4位，所以它的方根有2位，然后，我們通過下面的方法來枚舉出它的整數根
00*00=0<1200
10*10=100<120020*20=400<120030*30=900<1200 40*40=1600>1200所以，這個根的十位就是3，然后，再枚舉個位
31*31=961<120032*32=1024<1200
33*33=1089<1200
34*34=1156<1200
35*35=1225>1200
所以，這個根就是34，因為平方增長的速度還是比較快的，所以速度沒有太大問題，這里有一個地方需要處理一下，如果一個數很長，那么它的方根的位數也比較長，在枚舉高位的時候，我們沒有必要把后面的0都加上，因為那樣會影響速度，其實0的個數完全可以算出來，然后將0的個數一起送入比較函數比較即可，這樣可以提高速度
比較：上面我們說過，比較函數接受的兩個數只有一個是完整的數，另外一個實際上是高幾位的平方和0的個數，但處理方式差不多，都是先比較位數，位數大數就大，位數一樣就逐位比較，只要別忘了比較那一堆0就好了，最后其實不用把情況分的太清楚，只要返回0，1就行，因為只有當一個數大于n的時候才對我們有意義
#include<iostream>#include<string>#include<cstring>using namespace std;string strMul(string a,string b){ string result=""; int len1=a.length(); int len2=b.length(); int i,j; int num[500]={0}; for(i=0;i<len1;i++) for(j=0;j<len2;j++) { num[len1-1+len2-1-i-j]=num[len1-1+len2-1-i-j]+(a[i]-'0')*(b[j]-'0'); } //for(i=0;i<5;i++) //cout<<num[i]<<' '; //cout<<endl; for(i=0;i<len1+len2;i++) { num[i+1]=num[i+1]+num[i]/10; num[i]=num[i]%10; } //for(i=0;i<5;i++) //cout<<num[i]<<' '; for(i=len1+len2-1;i>=0;i--) { if(num[i]!=0) break; } for(;i>=0;i--) { result=result+(char)(num[i]+'0'); } return result;}int strCmp(string a,string b,int pos){ int i; //cout<<a<<endl; //cout<<a.length()<<' '<<b.length()<<endl; if(a.length()+pos>b.length()) return 1; if(a.length()+pos<b.length()) return 0; if(a.length()+pos==b.length()) { for(i=0;i<a.length();i++) { if(a[i]<b[i]) return 0; if(a[i]==b[i]) continue; if(a[i]>b[i]) return 1; } }}string strSqrt(string a){ string result=""; int i; int len=a.length(); if(len%2==0) len=len/2; else len=len/2+1; for(i=0;i<len;i++) { result=result+'0'; while(strCmp(strMul(result,result),a,2*(len-1-i))!=1) { if(result[i]==':') break; result[i]++; } result[i]--; } return result;}int main(){ string n,m; cin>>n>>m; cout<<strMul(strSqrt(n),strSqrt(m))<<endl; //cout<<strMul("35","35")<<endl; //cout<<strCmp("1024","1200",0); //cout<<strSqrt("9801"); return 0;}新聞熱點
疑難解答
圖片精選
