首页 > 代码库 > 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 (同余定理)