首页 > 代码库 > hdu 3501 容斥原理或欧拉函数
hdu 3501 容斥原理或欧拉函数
Calculation 2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2181 Accepted Submission(s): 920
Problem Description
Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.
Input
For each test case, there is a line containing a positive integer N(1 ≤ N ≤ 1000000000). A line containing a single 0 follows the last test case.
Output
For each test case, you should print the sum module 1000000007 in a line.
Sample Input
340
Sample Output
02
Author
GTmac
Source
2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT
题目大意：给一个数n求1到n-1之间与它不互质的数之和mod(1000000007)。
解题思路：我首先想到的是把n质因数分解成n=a1^p1*a2^p2....*an^pn的形式，那么把与他含有共同因子的数之和算出来，这里面有重复的，所以用容斥原理计算。
一个数的欧拉函数phi(n),根据gcd(n,i)==1,gcd(n,n-i)==1,所以与n互质的数都是成对出现的（他们的和等于n）。
1 //欧拉函数 2 #include <stdio.h> 3 #include <math.h> 4 5 typedef __int64 LL; 6 const int Mod=1000000007; 7 8 LL euler_phi(LL n) 9 {10 LL m=(LL)sqrt(n*1.0);11 LL ans=n;12 for(int i=2;i<=m;i++) if(n%i==0)13 {14 ans=ans/i*(i-1);15 while(n%i==0) n/=i;16 }17 if(n>1) ans=ans/n*(n-1);18 return ans;19 }20 21 int main()22 {23 LL n;24 while(~scanf("%I64d",&n),n)25 {26 LL phi=euler_phi(n);27 LL t1=(n*phi/2)%Mod;28 LL t2=(n*(n+1)/2-n)%Mod;29 LL ans=(t2-t1+Mod)%Mod;30 printf("%I64d\n",ans);31 }32 return 0;33 }
1 //容斥原理 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 6 typedef __int64 LL; 7 const int Mod=1000000007; 8 const int maxn=100000; 9 bool flag[maxn];10 int prime[maxn],num,n;11 int factor[100],cnt;12 bool vis[100];13 LL ans,temp;14 15 void get_prime()16 {17 num=0;memset(flag,true,sizeof(flag));18 for(int i=2;i<maxn;i++)19 {20 if(flag[i]) prime[num++]=i;21 for(int j=0;j<num&&prime[j]*i<maxn;j++)22 {23 flag[i*prime[j]]=false;24 if(i%prime[j]==0) break;25 }26 }27 }28 29 void get_factor()30 {31 cnt=0;32 int i,top=(int)sqrt(n*1.0),t=n;33 for(i=0;i<num && prime[i]<=top;i++)34 {35 if(t%prime[i]==0)36 {37 factor[cnt++]=prime[i];38 while(t%prime[i]==0)39 t/=prime[i];40 }41 }42 if(t>1) factor[cnt++]=t;43 }44 45 void dfs(int now,int top,int start,LL s)46 {47 if(now==top)48 {49 LL t=(n-1)/s;50 LL a=((t+1)*t/2)%Mod;51 LL b=(a*s)%Mod;52 temp=(temp+b)%Mod;53 return ;54 }55 for(int j=start;j<cnt;j++)56 {57 if(!vis[j])58 {59 vis[j]=true;60 dfs(now+1,top,j+1,s*factor[j]);61 vis[j]=false;62 }63 }64 return ;65 }66 67 void solve()68 {69 ans=0;70 int c=1;71 for(int i=1;i<=cnt;i++)72 {73 memset(vis,false,sizeof(vis));74 temp=0;dfs(0,i,0,1);75 ans=(((ans+c*temp)%Mod)+Mod)%Mod;76 c=-c;77 }78 }79 80 int main()81 {82 get_prime();83 while(scanf("%d",&n),n)84 {85 get_factor();86 solve();87 printf("%I64d\n",ans);88 }89 return 0;90 }
hdu 3501 容斥原理或欧拉函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。