CSU - 1803 —— 数学题

题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1803

Description

给出正整数 n 和 m，统计满足以下条件的正整数对 (a,b) 的数量：

1. 1≤a≤n,1≤b≤m;

2. a×b 是 2016 的倍数。

Input

输入包含不超过 30 组数据。

每组数据包含两个整数 n,m (1≤n,m≤109).

Output

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

Sample Input

32 63

2016 2016

1000000000 1000000000

Sample Output

1

30576

7523146895502644

题解：

x，y分别对2016取余，如果x*y 是2016的倍数的话，那么(2016*k + x)*y也是2016的倍数。

所以只需要统计这n个数之内，对2016取余后的数所出现的次数就可以了。

分两部分统计：

1.对于1~2016*k（k>=1）的数来说，2016的每个余数都已经出现了k遍，所以每个余数的出现次数都+k；

2.对于余下不足凑成2016个数的数来说，只需要把他们%2016的余数所出现的次数+1就可以了；

最后再对两个集合进行枚举相乘，看看是否为2016的倍数就可以了。

做过类似的题：http://blog.csdn.net/dolfamingo/article/details/62890375

代码如下：

#include<iostream>//CSU 1803 2016

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define LL long long

using namespace std;

int a[2020], b[2020];

int main()

{

    int n, m,rn,rm;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        rn = n/2016;

        rm = m/2016;

        for(int i = 0; i<2016; i++)//看2016出现了多少次， 每一次2016当中所有余数都会出现一遍

        {

            a[i] = rn;

            b[i] = rm;

        }

        rn = n%2016;

        rm = m%2016;

        for(int i = 1; i<=rn; i++) a[i]++;

        for(int i = 1; i<=rm; i++) b[i]++;

        LL ans = 0;

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

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

        {

            if((i*j)%2016==0)

                ans += (LL)a[i]*(LL)b[j];

        }

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

    }

}

巴特西