1803: 2016(容斥原理实现)

1803: 2016

         Time Limit: 5 Sec     Memory Limit: 128 Mb     Submitted: 1406     Solved: 807    

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

Hint

Source

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

这个题目直接枚举g=gcd(a,2016)即可

2016=2*2*2*2*2*3*3*7,所以g有6*3*2=36种情况。

对于每个g,求a满足gcd(a,2016)恰好是g,求b使得2016| a*b

一,求a满足gcd(a,2016)恰好是g

即求1,2,3......n/g这些数中,有多少个和2016/g互质,用容斥原理即可

二,求b使得2016| a*b

即求1,2,3......m这些数中,有多少个是2016/g的倍数,答案就是m*g/2016


//数学重要的还是建模,果然叫我写个容斥,还不如要我写个暴力,而且我只会套路
#include
#include
using namespace std;
#define ll long long
const int mn=36;
int x,y;
int g[]=
{1,7,3,21,9,63,2,14,6,42,18,126,4,28,12,84,36,
252,8,56,24,168,72,504,16,112,48,336,144,1008,
32,224,96,672,288,2016};//36个 
inline int fun(int x,int b)
{
	//求[1,x]与b互质的个数
	ll x2,x3,x7,x23,x27,x37,x237;
	x2=x3=x7=x23=x27=x37=x237=0;
	if(b%2==0) x2=x/2;
	if(b%3==0) x3=x/3;
	if(b%7==0) x7=x/7;
	if(b%6==0) x23=x/6;
	if(b%14==0) x27=x/14;
	if(b%21==0) x37=x/21;
	if(b%42==0) x237=x/42;
	return x-x2-x3-x7+x23+x27+x37-x237;
}
int main(){
	while(~scanf("%d%d",&x,&y))
	{
		ll ans=(ll)x/2016*y;//1是不满足容斥的,首先处理掉,注意溢出 
		for(int i=0;i<35;++i)
		{
			//求出1...x/g[i]和g[i]互质的个数.即求x满足gcd(x,2016)恰好是g[i]
			ll m=fun(x/g[i],2016/g[i]);
			//求出个数 
			ans+=m*(y/(2016/g[i]));
		}
		printf("%lldn",ans);
	}
	return 0;
}


未经允许不得转载!1803: 2016(容斥原理实现)