1803: 2016
Time Limit: 5 Sec Memory Limit: 128 Mb Submitted: 1406 Solved: 807Description
给出正整数 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(容斥原理实现)