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 ).

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[];

long long  b[];

int main(){

    int n,m;

    while(~scanf("%d%d",&n,&m)){

        memset(a,,sizeof(a));

        memset(b,,sizeof(b));

        //  计算 1~n 中对2016求余 各余数的个数

        int c = n/;

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

            a[i] = c;

        n = n%;

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

            a[i]++;

        //  计算 1~m 中对2016求余 各余数的个数

        int d = m/;

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

            b[i] = d;

        m = m%;

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

            b[i]++;

        long long sum = ;

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

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

                if(i*j% == )

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

        printf("%lld\n",sum);

    }

    return ;

}