CSU 1803 2016（16湖南省赛）(同余定理)

太过爱你忘了你带给我的痛 2022-07-14 08:00 123阅读 0赞

## 1803: 2016 ##

Time Limit: 5 Sec Memory Limit: 128 MB  
Submit: 638 Solved: 419  
\[ [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 9).

## Output ##

对于每组数据，输出一个整数表示满足条件的数量。

## Sample Input ##

32 63
    2016 2016
    1000000000 1000000000

## Sample Output ##

1
    30576
    7523146895502644

## HINT ##

## Source ##

[湖南省第十二届大学生计算机程序设计竞赛][Link 1]

题解：

由同余定理得  
(a\*b)%p=((a%p)\*(b%p))%p；

所以(a\*b)%p=((a%2016)\*(b%2016))%2016;

这样,我们就可以将数据范围控制在2016以内。  
即记录\[1,n\]内 mod 2016 = i的个数a\[i\]  
以及记录\[1,m\]内 mod 2016 = i的个数b\[i\]  
时间复杂度为O(2016)。  
然后，我们只要将(i\*j)%2016==0的所有情况a\[i\]\*b\[j\]统计求和就可以了。

AC代码：

//#include<bits/stdc++.h>
    #include<cstdio>
    using namespace std;
    long long a[2016],b[2016];  
    int main()  
    {  
        int n,m,i,j;  
        long long ans;  
        while(~scanf("%d%d",&n,&m))  
        {  
            ans=0;  
            for(i=0;i<2016;i++)  
                a[i]=n/2016,b[i]=m/2016;  
                
            for(i=1;i<=n%2016;i++)  a[i]++;  
            for(i=1;i<=m%2016;i++)  b[i]++;  
            
            for(i=0;i<2016;i++)  
                for(j=0;j<2016;j++)  
                    if((i*j)%2016==0)  
                        ans+=a[i]*b[j];  
            printf("%lld\n",ans);  
        }  
        return 0;  
    }

[Submit]: http://acm.csu.edu.cn/OnlineJudge/submitpage.php?id=1803
[Status]: http://acm.csu.edu.cn/OnlineJudge/problemstatus.php?id=1803
[Web Board]: http://acm.csu.edu.cn/OnlineJudge/bbs.php?pid=1803
[Link 1]: http://acm.csu.edu.cn/OnlineJudge/problemset.php?search=%E6%B9%96%E5%8D%97%E7%9C%81%E7%AC%AC%E5%8D%81%E4%BA%8C%E5%B1%8A%E5%A4%A7%E5%AD%A6%E7%94%9F%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E7%AB%9E%E8%B5%9B