首页 > 代码库 > CSU 1803 2016（同余公式）2016年湖南省第十二届大学生计算机程序设计竞赛
CSU 1803 2016（同余公式）2016年湖南省第十二届大学生计算机程序设计竞赛
题意
给出正整数 n 和 m，统计满足以下条件的正整数对 (a,b) 的数量：
1. 1 ≤ a ≤ n, 1 ≤ b ≤ m;
2. a×b 是 2016 的倍数。
样例输入
32 63
2016 2016
1000000000 1000000000
样例输出
1
30576
7523146895502644
思路
由同余公式可得
a * b % 2016 = (a % 2016) * (b % 2016) % 2016
所以如果 x*y 是2016的倍数的话，那么(2016*k + x)*y也是
那么只需要统计1-n的各个数模2016的余数的出现次数，就可以把枚举时的循环次数缩小到2016*2016。
1 #include <cstdio> 2 typedef long long int LL; 3 const int N = 2016; 4 int a[N], b[N]; 5 LL ans; 6 int main(void) 7 { 8 int n, m, nx, mx; 9 while(~scanf("%d %d", &n, &m))10 {11 nx = n / N;12 mx = m / N;13 for(int i=0; i<N; ++i)14 a[i] = nx, b[i] = mx;15 nx = n % N;16 mx = m % N;17 for(int i=1; i<=nx; ++a[i++]);18 for(int i=1; i<=mx; ++b[i++]);19 ans = 0;20 for(int i=0; i<N; ++i)21 for(int j=0; j<N; ++j)22 if(i*j%N == 0)23 ans += (LL)a[i] * b[j];24 printf("%lld\n", ans);25 }26 return 0;27 }
CSU 1803 2016（同余公式）2016年湖南省第十二届大学生计算机程序设计竞赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。