数论 + 容斥定理
1435.互质
Time Limit: 1000 MS MemoryLimit: 65536 K
Total Submissions: 126 (48users) Accepted: 30(26 users)
[ MySolution ]
Description
欧拉函数在数论中有着重要的地位, 一个数的欧拉函数的值, 代表着与这个数互质且不大于这个数的正整数的个数, 例如6的欧拉函数的值为2, 因为比6小且与6互质的数只有1和5。当然, 这道题目的要求并不是需要你求某个数的欧拉函数的值, 而是给定你正整数A、L、R, 你需要求出在区间[L, R]的范围内有多少个数与A互质。
Input
输入只有一行, 分别为3个正整数A、L、R。(1 <= L <= R <= 1,000,000,000 , 2 <= A <= 1,000,000,000)
Output
输出在区间[L, R]范围内有多少个数与数字A互质。
Sample Input
6 1 6
Sample Output
2
Source
doraemon @ xmu
/*类型：欧拉函数 ~ 容斥原理依稀记得袁神教我的容斥原理，但是我忘了方法，今天按照自己的理解还是写了出来，没什么的，挺简单的，重点是奇偶判断 。。。 */#include<iostream>#include<algorithm>#include<cstdio>#include<cmath>#define manx 1025using namespace std;int f[manx],p[20],num,ans;int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b);}void fan(int n){////求素数因子 for(int i=2;i*i<=n;i++){ if(n%i==0) p[++num]=i; while(n%i==0) n/=i; } if(n>1) p[++num]=n;}void dfs(int st,int ed,int val,int k){////容斥定理 if(k%2) f[ans++]=val;//////奇偶判断 else f[ans++]=-val; if(st>ed) return; for(int i=st;i<=ed;i++)////组合得到因子 dfs(i+1,ed,p[i]*val,k+1); ///注意其方法 }int main(){ long long a,l,r; while(cin>>a>>l>>r){ if(l==r){///特殊情况 if(gcd(a,l)==1)printf("1\n"); else printf("0\n"); continue; } num = 0; ans=0; memset(f,0,sizeof(f)); fan(a); for(int i=1;i<=num;i++) dfs(i+1,num,p[i],1); long long sum=0,tall=0; ///sum表示欧拉互质数，tall表示要求的总互质数 for(int i=0;i<ans;i++) sum+=a/f[i];////容斥定理，组合求出某个因子的 sum = a - sum; if(r-l>a) tall += (r-l)/a*sum; ///周期相减 r %= a; l %= a; if(r==0) r=a; ///整倍临界点 long long sum1=0,sum2=0;///sum1表示 1~l，sum2表示1~r for(int i=0;i<ans;i++){ sum1+=l/f[i]; sum2+=r/f[i]; } sum1 = l-sum1; sum2 = r-sum2; tall += sum2-sum1; if(r<=l) tall+=sum;///取补集 if(l%a && gcd(l,a)==1) tall++; ///闭区间 cout<<tall<<endl; }}