hdu 1695 综合数论 欧拉函数 分解质因子 容斥原理 打印素数表 帅呆了的一个题目 详解

GCDTime Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3112    Accepted Submission(s): 1095


Problem DescriptionInputOutputSample InputSample OutputSourceRecommend/*题目大意：给你a, b, c, d, k; 找出这样的一队 x, y， 使得 gcd(x , y) = k, 并且x ∈[1, b], y ∈ [1, d], 问有多少对符合要求的(x, y)。------------------------------------------思路: 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范围内能整除的个数(质数分解和容斥关系)，*/#include <iostream>#include <stdio.h>#include <memory.h>#include<math.h>#include <vector>using namespace std;const int N = 100005;typedef long long LL;#define maxn 100005LL phi[N];vector<LL> link[N];int vis[1000000+5],c; LL prime[79000]; void get_prime() //打印素数表模板{ int i,j,n,m; c=0; n=1000000; m=(int)sqrt(n+0.5); memset(vis,0,sizeof(vis)); for(i=2;i<=m;i++) if(!vis[i]) { for(j=i*i;j<=n;j+=i) vis[j]=1; } for(i=2;i<=n;i++) if(!vis[i]) prime[c++]=i; } void get_PHI() //模板 得到1->n之内 与n互质的数的个数 存入phi[n]{ int i,j; for (i = 1; i <= maxn; i++) phi[i] = i; for (i = 2; i <= maxn; i += 2) phi[i] /= 2; for (i = 3; i <= maxn; i += 2) if(phi[i] == i) { for (j = i; j <= maxn; j += i) phi[j] = phi[j] / i * (i - 1); } }void init() //求每一个数的质因数，vector储存 { LL i, j, k; for(i = 1; i < N; i++)//求n的质因数 也是模板 { k = i; for(j = 0; prime[j]*prime[j] <= k; j++) { if(k%prime[j] == 0) { link[i].push_back(prime[j]); while(k%prime[j] == 0) k /= prime[j]; } if(k == 1) break; } if(k > 1) link[i].push_back(k); }}LL make_ans(LL num,LL n)//1到num中的所有数与n的m个质因子不互质的数的个数 注意是不互质哦 容斥原理{ LL ans=0,tmp,i,j,flag; for(i=1;i<(LL)(1<<link[n].size());i++) { //用二进制来1,0来表示第几个素因子是否被用到,如m=3，三个因子是2,3,5，则i=3时二进制是011，表示第2、3个因子被用到 tmp=1,flag=0; for(j=0;j<link[n].size();j++) if(i&((LL)(1<<j)))//判断第几个因子目前被用到 flag++,tmp*=link[n][j];//第j个质因子link[n][j] if(flag&1)//容斥原理，奇加偶减 ans+=num/tmp; else ans-=num/tmp; } return ans; } int main(){ LL i, a, b, c, d, k, sum, t, zz = 1;//longlong型的数据 可以用%I64d 来输入输出 get_prime();get_PHI(); init(); scanf("%I64d", &t); while(t--) { scanf("%I64d %I64d %I64d %I64d %I64d", &a, &b, &c, &d, &k); if(k == 0 || k > b || k > d) { printf("Case %I64d: 0\n", zz++); continue; } if(b > d) swap(b, d);//保持d较大 b /= k; d /= k; sum = 0; for(i = 1; i <= b; i++) { sum += phi[i]; } for(i = b+1; i <= d; i++) { sum += b - make_ans(b, i); } printf("Case %I64d: %I64d\n", zz++, sum); } return 0;}