題目地址：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1803?

?

Knowledge Point:

　　同余定理：兩個(gè)整數(shù)a、b，若它們除以整數(shù)m所得的余數(shù)相等，則稱(chēng)a與b對(duì)模m同余或a同余于b模m。記作?a≡b(mod m)；

　　　　加法運(yùn)用：?(a + b) % m = (a % m + b % m) % m

?

　　　　乘法運(yùn)用：?(a * b) % m = ((a % m) * (b % m)) % m

?

?

　　　　　高精度取模：?一個(gè)高精度數(shù)對(duì)一個(gè)數(shù)取余，可以把高精度數(shù)看成各位數(shù)的權(quán)值與個(gè)位數(shù)乘積的和。

　　　　　　　　　　eg: 1234? = ((1*10+2) *10+3) *10+4, 綜合運(yùn)用上面的加法和乘法運(yùn)用公式求解；

1 string a = "1234"; 2 int ans = 0; 3 for(int i = 0; i < a.length; i++){ 4 ans = (ans * 10 + a[i] - '0') % mod; 5 } 6 cout << ans << endl;

?

　　　　　快速冪取模：? 將冪拆解為多個(gè)底數(shù)的平方次的積，如果指數(shù)為偶數(shù)，把指數(shù)除以2，并讓底數(shù)的平方次取余，如果指數(shù)為奇數(shù)，就把多出來(lái)的底數(shù)記錄下來(lái)，再執(zhí)行偶數(shù)次的操作。

1 int PowerMod(int a, int b, int mod){ 2 int ans = 1; //a-底數(shù)，b-質(zhì)數(shù) 3 a = a % mod; 4 while(b > 0){ 5 if(b&1){ 6 ans *= (a % mod); 7 } 8 b >>= 1; 9 a = (a * a) % mod； 10 } 11 ans %= mod; 12 return ans; 13 }

?

?

Summarize：

　　1. 同余定理運(yùn)用；

　　2. 數(shù)據(jù)范圍爆 int，使用 long long；

　　3. 如果 (i*j)%mod==0 則有 (i*j+mod)%mod==0 ;

?

　　一開(kāi)始我選擇求2016的所有因數(shù)，循環(huán)將 n 和 m 中因數(shù)的倍數(shù)個(gè)數(shù)相乘再將所有結(jié)果相加。但可能出現(xiàn)某一個(gè)數(shù) x 同時(shí)是多個(gè)因數(shù)的公倍數(shù)，且

2016/x 恰好也是多個(gè)因數(shù)的公倍數(shù)，出現(xiàn)重復(fù)，故該方法不能通過(guò)。

?

附代碼：

1 /* 2 題目地址：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1803 3 4 2016 5 給出正整數(shù) n 和 m，統(tǒng)計(jì)滿(mǎn)足以下條件的正整數(shù)對(duì) (a,b) 的數(shù)量： 6 1. 1≤a≤n,1≤b≤m; 7 2. a×b 是 2016 的倍數(shù)。 8 輸入每組數(shù)據(jù)包含兩個(gè)整數(shù) n,m (1≤n,m≤10e9). 9 10 Sample Input 11 32 63 12 2016 2016 13 1000000000 1000000000 14 15 Sample Output 16 1 17 30576 18 7523146895502644 19 */ 20 #include<iostream> 21 #include<cstring> 22 #include<algorithm> 23 #include<vector> 24 #include<queue> 25 #include<cmath> 26 using namespace std; 27 28 #define LL long long 29 const int N = 2016; 30 LL n,m,ans; 31 LL a[N], b[N]; 32 33 int main() 34 { 35 ios::sync_with_stdio(false); 36 37 while(cin>>n>>m) 38 { 39 ans=0; 40 for(int i=0; i<N; i++) 41 { a[i]=n/N; b[i]=m/N;} 42 for(int i=1; i<=n%N; i++) a[i]++; 43 for(int i=1; i<=m%N; i++) b[i]++; 44 45 for(int i=0; i<N; i++) 46 for(int j=0; j<N; j++) 47 if(i*j%N == 0) 48 ans += a[i]*b[j]; 49 cout<<ans<<endl; 50 } 51 52 return 0; 53 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/liubilan/p/9384032.html

總結(jié)

以上是生活随笔為你收集整理的十二届 - CSU 1803 ：2016（同余定理）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。