GCD
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5064 Accepted Submission(s): 1818
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.
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.
1
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).
参考: http://blog.****.net/xiaotaoqibao/article/details/5772486
题目意思不难已知给定k,x,y求 1<=a<=x 1<=b<=y 中满足 gcd(a,b)=k 的(a,b)对数。(注意数对是无序的)。 1<=x,y<=10w, 0<=k<=10w
题目有比较恶心的一点,数据有k==0的,这时显然答案是0,没有2个数的gcd为0。
首先,gcd是没啥用的。因为约掉gcd后两个数互质。于是我们可以让x/=k y/=k并且假设 x<=y
然后题目变成了 2个数分别在区间[1..x]和[1..y]中的互质数有多少对。
大体思路:
枚举[1..y]中每个数i 判断[1..min(x,i)]中有多少数与i互质,统计个数。(注意,枚举的是比较大的区间[1..y])。
显然如果i是质数,则[1..min(x,i)]中与i互质的个数是全体的个数或者i-1个。(取决于x和i的大小)。
当i不是质数时,i分解质因数后,质因数的次数不影响结果。我们看另外那个区间有多少个和i不互质(减一下就好了),于是我们只要看另外那个区间中有多少个数是i质因数的倍数就好了。
区间[1..w]中 p的倍数 显然有 w/p个。
我们枚举i的质因数利用容斥原理:
看另外那个区间有多少个数与i不互质。
容斥原理的具体如下:
区间中与i不互质的个数 = (区间中i的每个质因数的倍数个数)-(区间中i的每两个质因数乘积的倍数)+(区间中i的每3个质因数的成绩的倍数个数)-(区间中i的每4个质因数的乘积)+...
于是问题变成了统计每个数的不同质因数的个数而忽略次数。这个可以用筛法。具体做法如下:
对每个数保存一个真质因数的列表。初始每个列表的长度为0。然后从2开始,分别检查每个数的列表长度,如果列表长度不为0,则这个数是合数,跳过;如果这个长度为0,则我们找到了一个质数,同时再把这个数的倍数(不包含本身)的列表里加入这个数。
这样筛一次下来,我们保存了每个数的真质因数列表,问题得到解决,还要注意结果用要用__int64。
///218MS 7256K 1385 B G++
//容斥原理+欧拉函数
#include<stdio.h>
#include<string.h>
#include<string.h>
#define N 100005
int ss[N][]; //质因数
int num[N]; //不同质因数个数
__int64 euler[N]; //euler[i]:[1,i]的欧拉数和
void init()
{
memset(ss,,sizeof(ss));
memset(euler,,sizeof(euler));
euler[]=;
for(int i=;i<N;i++){
if(!euler[i]){ //质数
for(int j=i;j<N;j+=i){
if(!euler[j]) euler[j]=j;
euler[j]=euler[j]*(i-)/i;
ss[j][num[j]++]=i; //记录质因数
}
}
euler[i]+=euler[i-];
//printf("*%d %d\n",i,euler[i]);
}
}
__int64 dfs(int a,int b,int q) //容斥原理
{
__int64 res=;
for(int i=a;i<num[q];i++){
res+=b/ss[q][i]-dfs(i+,b/ss[q][i],q);
}
return res;
}
int main(void)
{
int t,cas=;
int a,b,c,d,k;
init();
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(k==){
printf("Case %d: 0\n",cas++);continue;
}
b/=k;
d/=k; //题目变成[1,b]与[1,d]间的互质的数有多少对
if(b>d){
int temp=b;b=d;d=temp;
}
__int64 res=euler[b];
for(int i=b+;i<=d;i++){
res+=b-dfs(,b,i);
}
printf("Case %d: %I64d\n",cas++,res);
}
return ;
}