2016

Problem Description：

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

1≤a≤n,1≤b≤m;
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

这题赛后发现还是可以做出来的，但比赛时看了近1小时都没思路，果然比赛时平常心很重要。

【题目链接】CSU 1803 2016

【题目类型】模运算

&题解：

可以求出在[1,N]中，模为[1,2016]的数的个数; 以及在[1,M]中，模为[1,2016]的数的个数。分别存进a b数组，

因为x ∗y%2016=x%2016 ∗y%2016，接下来判断(x%2016 ∗y%2016)%2016是否为0，如果是那么他们的情况就有a[i]*b[j]种（注意：这块一定要用ll，因为这块最大的话都是1e6，乘起来就是1e12，会爆int），最后相加，输出就好。

【时间复杂度】O(2016^2)

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define rez(i,a,b) for(int i=(a);i<=(b);i++)

#define PI(A) cout<<(A)<<endl;

const int MAXN = 2016 + 5 ;

int a[MAXN],b[MAXN];

int n,m;

void Solve()

{

	while(~SII(n,m))

	{

		cle(a,0),cle(b,0);

		rez(i,1,2016) a[i]=n/2016;

		rez(i,1,2016) b[i]=m/2016;

		rez(i,1,n%2016) a[i]++;

		rez(i,1,m%2016) b[i]++;

		ll ans=0;

		rez(i,1,2016)

		rez(j,1,2016)

		{

			if (i*j%2016==0)

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

		}

		PI(ans)

	}

}

int main()

{

	Solve();

	return 0;

}

秒客网

CSU 1803 2016（数论）