csu 1803(余数分类)

1803: 2016

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 565 Solved: 364
[Submit][Status][Web Board]

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

总感觉这个题特别可惜,做出来就是金奖了,余数分类 ,刚开始就想歪了 ,这锅我的背,这个题我一直都在考虑...我把2016给分解了...起码浪费了3小时在这个题,不然别的题也不至于看都没看,可能还可以多A一些题.

a*b%2016 = （a%2016*b%2016）%2016 所以它们的余数都在 [0,2015] ，按照余数分类,在 2016*2016 的时间内就可以解出来了.a的循环节是2016,b也是2016.

所以所有的余数个数都是 a/2016,b/2016,多出来的那一截再去补上+1,然后根据乘法原理算即可.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int mod1[],mod2[]; ///按照余数分类

int main()

{

    int a,b;

    while(scanf("%d%d",&a,&b)!=EOF){

        int c = a/,d = b/;

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

            mod1[i] = c,mod2[i] = d;

        }

        c = a%,d = b%;

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

            mod1[i]++;

        }

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

            mod2[i]++;

        }

        LL ans = ;

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

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

                if(i*j%==){

                    ans += (LL)mod1[i]*mod2[j];

                }

            }

        }

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

    }

    return ;

}

巴特西