首页 > 代码库 > 2016湖南省赛----A 2016 (同余定理)
2016湖南省赛----A 2016 (同余定理)
2016湖南省赛----A 2016 (同余定理)
Description
给出正整数 n 和 m,统计满足以下条件的正整数对 (a,b) 的数量:
1. 1≤a≤n,1≤b≤m;
2. a×b 是 2016 的倍数。
Input
输入包含不超过 30 组数据。
每组数据包含两个整数 n,m (1≤n,m≤10 9).
Output
对于每组数据,输出一个整数表示满足条件的数量。
Sample Input
32 63
2016 2016
1000000000 1000000000
Sample Output
1 30576 7523146895502644
思路:
同余定理 : 设 a%2016 = c1 , b%2016 = c2, 若,c1*c2%2016 == 0,则 a*b%2016 == 0;
根据余数不同可将 1~n 与 1~m 按余数进行分类,统计 1~n 与 1~m 对2016求余 各余数的个数,分别为 a[1],a[2] .....a[2016],
b[1],b[2]......b[2016]。根据同于定理,若 i*j%2016 == 0; 则可知余数为i,与余数为j的数相乘为2016的倍数,且共有a[i]*b[j]
种方式。
具体实现如下:
#include <iostream> #include <stdio.h> #include <stdio.h> using namespace std; long long a[2017]; long long b[2017]; int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); // 计算 1~n 中对2016求余 各余数的个数 int c = n/2016; for(int i=1;i<=2016;i++) a[i] = c; n = n%2016; for(int i = 1;i<=n;i++) a[i]++; // 计算 1~m 中对2016求余 各余数的个数 int d = m/2016; for(int i = 1;i<=2016;i++) b[i] = d; m = m%2016; for(int i = 1;i<=m;i++) b[i]++; long long sum = 0; for(int i = 1;i<=2016;i++) for(int j = 1;j<=2016;j++) if(i*j%2016 == 0) sum+=a[i]*b[j]; printf("%lld\n",sum); } return 0; }
2016湖南省赛----A 2016 (同余定理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。