十二届 - CSU 1803 ：2016（同余定理）

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

Knowledge Point:

　　同余定理：两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对模m同余或a同余于b模m。记作 a≡b(mod m)；

　　　　加法运用： (a + b) % m = (a % m + b % m) % m

　　　　乘法运用： (a * b) % m = ((a % m) * (b % m)) % m

　　　　　高精度取模：一个高精度数对一个数取余，可以把高精度数看成各位数的权值与个位数乘积的和。

　　　　　　　　　　eg: 1234 = ((1*10+2) *10+3) *10+4, 综合运用上面的加法和乘法运用公式求解；

 string a = "1234";

 int ans = ;

 for(int i = ; i < a.length; i++){

     ans = (ans *  + a[i] - '') % mod;

 }

 cout << ans << endl;

　　　　　快速幂取模：将幂拆解为多个底数的平方次的积，如果指数为偶数，把指数除以2，并让底数的平方次取余，如果指数为奇数，就把多出来的底数记录下来，再执行偶数次的操作。

 int PowerMod(int a, int b, int mod){

     int ans = ;    //a-底数，b-质数

     a = a % mod;

     while(b > ){

         if(b&){

             ans *= (a % mod);

         }

         b >>= ;

         a = (a * a) % mod；

     }

     ans %= mod;

     return ans;

 }

Summarize：

　　1. 同余定理运用；

　　2. 数据范围爆 int，使用 long long；

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

　　一开始我选择求2016的所有因数，循环将 n 和 m 中因数的倍数个数相乘再将所有结果相加。但可能出现某一个数 x 同时是多个因数的公倍数，且

2016/x 恰好也是多个因数的公倍数，出现重复，故该方法不能通过。

附代码：

 /*

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

 2016

 给出正整数 n 和 m，统计满足以下条件的正整数对 (a,b) 的数量：

     1. 1≤a≤n,1≤b≤m;

     2. a×b 是 2016 的倍数。

 输入每组数据包含两个整数 n,m (1≤n,m≤10e9).

 Sample Input

 32 63

 2016 2016

 1000000000 1000000000

 Sample Output

 1

 30576

 7523146895502644

 */

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define LL long long

 const int N = ;

 LL n,m,ans;

 LL a[N], b[N];

 int main()

 {

     ios::sync_with_stdio(false);

     while(cin>>n>>m)

     {

         ans=;

         for(int i=; i<N; i++)

             { a[i]=n/N; b[i]=m/N;}

         for(int i=; i<=n%N; i++) a[i]++;

         for(int i=; i<=m%N; i++) b[i]++;

         for(int i=; i<N; i++)

             for(int j=; j<N; j++)

                 if(i*j%N == )

                     ans += a[i]*b[j];

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

十二届 - CSU 1803 ：2016（同余定理）

最新文章

热门文章