hdu 1695 容斥原理或莫比乌斯反演
2024-08-30 06:31:15
GCD
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5310 Accepted Submission(s): 1907
Problem Description
Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you're only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.
Yoiu can assume that a = c = 1 in all test cases.
Input
The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.
Output
For each test case, print the number of choices. Use the format in the example.
Sample Input
2
1 3 1 5 1
1 11014 1 14409 9
1 3 1 5 1
1 11014 1 14409 9
Sample Output
Case 1: 9
Case 2: 736427
Case 2: 736427
Hint
For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).
Source
题目大意:求在1<=x<=b,1<=y<=d上gcd(x,y)=k的(x,y)对数。
/************容斥原理*************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std; typedef __int64 LL;
const int maxn=1e5+;
int phi[maxn],prime[maxn],factor[],num;
bool flag[maxn];
void swap(int &a,int &b){ int t=a;a=b;b=t;} void init()//欧拉筛选
{
memset(flag,true,sizeof(flag));
phi[]=;
for(int i=;i<maxn;i++)
{
if(flag[i])
{
prime[num++]=i;
phi[i]=i-;
}
for(int j=;j<num&&i*prime[j]<maxn;j++)
{
flag[i*prime[j]]=false;
if(i%prime[j]==)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-);
}
}
} void getfactor(int n,int &len)//质因数分解
{
int t=sqrt(n*1.0);len=;
for(int i=;i<num&&prime[i]<=t;i++)
{
if(n%prime[i]==)
{
factor[len++]=prime[i];
while(n%prime[i]==) n/=prime[i];
}
}
if(n>) factor[len++]=n;
} int getans(int a,int b)
{
int n;
int ans=;
getfactor(b,n);
for(int i=;i<(<<n);i++)//容斥原理
{
int cnt=,temp=;
for(int j=;j<n;j++)
{
if(i&(<<j))
{
cnt++;temp*=factor[j];
}
}
if(cnt&) ans+=a/temp;
else ans-=a/temp;
}
return a-ans;
} int main()
{
int i,a,b,c,d,k,t,icase=;
LL ans;num=;
init();
scanf("%d",&t);
while(t--)
{
scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
if(k==||k>b||k>d)
{
printf("Case %d: 0\n",++icase);
continue;
}
ans=;
b/=k;d/=k;
if(b>d) swap(b,d);
for(i=;i<=b;i++) ans+=phi[i];
for(i=b+;i<=d;i++) ans+=getans(b,i);
printf("Case %d: %I64d\n",++icase,ans);
}
return ;
}
/*************莫比乌斯反演****************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; typedef __int64 LL;
const int maxn=1e5+;
int prime[maxn],mu[maxn],num;
bool flag[maxn]; void init()
{
memset(flag,true,sizeof(flag));
mu[]=;
for(int i=;i<maxn;i++)
{
if(flag[i])
{
prime[num++]=i;mu[i]=-;
}
for(int j=;j<num&&i*prime[j]<maxn;j++)
{
flag[i*prime[j]]=false;
if(i%prime[j]==)
{
mu[i*prime[j]]=;
break;
}
else mu[i*prime[j]]=-mu[i];
}
}
} int main()
{
num=;
init();
int i,a,b,c,d,k,t,icase=;
scanf("%d",&t);
while(t--)
{
scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
if(k==||k>b||k>d)
{
printf("Case %d: 0\n",++icase);
continue;
}
b=b/k;d=d/k;
if(b>d) swap(b,d);
LL ans=,ans1=;
for(i=;i<=b;i++)
ans+=(LL)mu[i]*(b/i)*(d/i);
for(i=;i<=b;i++)
ans1+=(LL)mu[i]*(b/i)*(b/i);
ans-=ans1/;
printf("Case %d: %I64d\n",++icase,ans);
}
return ;
}
最新文章
- Dreamweaver 扩展开发: Calling a C++ function from JavaScript
- nancy中视图呈现 Html.Partial(RenderPage的替代品)
- ItemsSource绑定后ScrollViewer不复位
- Linux进程启动过程简析
- mybatis实战
- 剑指offer系列60---第一个只出现一次的字符
- C++ Tempatet之模板模型
- JavaScript无限极菜单
- Dev之ChartControl控件(一)
- BOM元素之window对象
- 晒下我在2017年所阅读的JavaScript书单
- PHP实现zip压缩打包下载
- 用SpringCloud进行微服务架构演进
- Python第8天
- 跨源资源共享(CORS)概念、实现(用Spring)、起源介绍
- python TCP socket套接字编程以及注意事项
- Android Studio开发第一篇QuickStart
- (转)RBAC权限表的设计
- Python之路PythonThread,第二篇,进程2
- python第三十二课——栈