csu 1803 2016 2016湖南省赛 A

Problem

acm.csu.edu.cn/csuoj/problemset/problem?pid=1803

vjudge.net/contest/161962#problem/A

Reference

www.cnblogs.com/wuwangchuxin0924/p/5838984.html

Meaning

问有多少个整数对（a，b），满足：1 <= a <= n，1 <= b <= m，a * b % 2016 = 0

Analysis

a = 2016 * x + i

b = 2016 * y + j

a * b = 2016 * ( 2016 * x * y + y * i + x * j ) + i * j

可见 a * b 能否整除 2016 取决于 i * j 是否整除 2016。

枚举 a 和 b 对 2016 的余数的乘积 i * j，如果这一对乘积能整除 2016，那么所有对 2016 余数为 i 和 j 的数相乘就都整除 2016。

Code

#include <iostream>
using namespace std;
const int MOD = 2016;

inline long long cal(int rest, int top)
{
	/* a 和 b 都不能为零，要特判 */
	return top / MOD + (rest && top % MOD >= rest);
}

int main()
{
	ios::sync_with_stdio(false);
	int n, m;
	while(cin >> n >> m)
	{
		long long ans = 0;
		for(int i=0; i<MOD; ++i)
			for(int j=0; j<MOD; ++j)
				if(i * j % MOD == 0)
					ans += cal(i, n) * cal(j, m);
		cout << ans << '\n';
	}
	return 0;
}