2016年湖南省第十二屆大學生計算機程序設計競賽Problem A 2016 找規律歸類，湖南省2016

2016年湖南省第十二屆大學生計算機程序設計競賽Problem A 2016 找規律歸類，湖南省2016

Problem A: 2016

Time Limit: 5 Sec  Memory Limit: 128 MB

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

 

    題目是全中文的，所以題意方面沒什麼好說的，也很好理解，主要是考慮做法了。首先數據很大，直接一個一個跑for循環是肯定不夠的，不過在樣例中把最大的一種情況告訴我們了，可以了解到long long定義是完全夠用的，然後再來考慮如何處理。

    因為題目要求的是兩個數相乘之後是否是2016的倍數，所以可以把兩邊分開來看，比如1~2016和2017~4032這兩組數據，雖然數字不同，但是這兩組和其他數字乘在一起之後判斷有多少數字為2016的倍數的話，結果是一樣的，所以可以把這兩組數都拆分開再來進行運算，這樣的話跑for循環只需要跑兩遍，只跑到2016就足夠了，其余的數再分出來用數組進行儲存，記錄下來一共有多少組1~2016，在結果上再乘以幾就可以了。

    下面AC代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long a[2030],b[2030];

int main()
{
    long long n,m;
    int i,j;
    long long k,t;
    long long cou;
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        cou=0;
        //分離n
        k=n/2016;
        t=n%2016;
        for(i=1;i<=t;i++)
        {
            a[i]=k+1;
        }
        for(i=t+1;i<=2016;i++)
        {
            a[i]=k;
        }
        //分離m
        k=m/2016;
        t=m%2016;
        for(i=1;i<=t;i++)
        {
            b[i]=k+1;
        }
        for(i=t+1;i<=2016;i++)
        {
            b[i]=k;
        }
        //計算
        for(i=1;i<=2016;i++)
        {
            for(j=1;j<=2016;j++)
            {
                if((i*j)%2016==0)
                    cou=cou+a[i]*b[j];
            }
        }
        cout<<cou<<endl;
    }
    return 0;
}