题意: 在1~a, 1~b中挑出(x,y)满足gcd(x,y) = k , 求(x,y) 的对数 , a,b<=10^5
思路: gcd(x, y) == k 说明x,y都能被k整除, 但是能被k整除的未必gcd=k , 必须还要满足
互质关系. 问题就转化为了求1~a/k 和 1~b/k间互质对数的问题
可以把a设置为小的那个数, 那么以y>x来保持唯一性(题目要求, 比如[1,3] = [3,1] )
接下来份两种情况:
1. y <= a , 那么对数就是 1~a的欧拉函数的累计和(容易想到)
2. y >= a , 这个时候欧拉函数不能用了,怎么做? 可以用容斥原理,把y与1~a互质对数问题转换为
y的质数因子在1~a范围内能整除的个数(质数分解和容斥关系)dfs一下即可.
- #include <iostream>
- #include <stdio.h>
- using namespace std;
- #define N 100005
- #define ll __int64
- ll eule[N];
- int p[N][15];
- int num[N];
- void init()
- {
- int i,j;
- eule[1]=1;
- for(i=2;i<N;i++)//筛选法得到数的素因子及每个数的欧拉函数值
- {
- if(!eule[i])
- {
- for(j=i;j<N;j+=i)
- {
- if(!eule[j])
- eule[j]=j;
- eule[j]=eule[j]*(i-1)/i;
- p[j][num[j]++]=i;
- }
- }
- eule[i]+=eule[i-1];
- }
- }
- ll DFS(int x,int MAX,int q) //求MAX内与q不互质的个数
- {
- int i;
- ll res=0;
- for (i=x;i<num[q];i++)
- {
- res+=MAX/p[q][i]-DFS(i+1,MAX/p[q][i],q);
- }
- return res;
- }
- int main()
- {
- int t,a,b,MAX,MIN,k,flag,i;
- __int64 res;
- init();
- scanf("%d",&t);
- flag=0;
- while(t--)
- {
- flag++;
- scanf("%d%d%d%d%d",&a,&a,&b,&b,&k);
- if(k==0)
- {
- printf("Case %d: 0\n",flag);
- continue;
- }
- MAX=a>b?a:b;
- MIN=a>b?b:a;
- MAX/=k;
- MIN/=k;
- res=eule[MIN];
- for(i=MIN+1;i<=MAX;i++)
- {
- res+=MIN-DFS(0,MIN,i);
- }
- printf("Case %d: %I64d\n",flag,res);
- }
- return 0;
- }