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

3
4
0

Sample Output

0
2

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）。

 //欧拉函数

 #include <stdio.h>

 #include <math.h>

 typedef __int64 LL;

 const int Mod=;

 LL euler_phi(LL n)

 {

     LL m=(LL)sqrt(n*1.0);

     LL ans=n;

     for(int i=;i<=m;i++) if(n%i==)

     {

         ans=ans/i*(i-);

         while(n%i==) n/=i;

     }

     if(n>) ans=ans/n*(n-);

     return ans;

 }

 int main()

 {

     LL n;

     while(~scanf("%I64d",&n),n)

     {

         LL phi=euler_phi(n);

         LL t1=(n*phi/)%Mod;

         LL t2=(n*(n+)/-n)%Mod;

         LL ans=(t2-t1+Mod)%Mod;

         printf("%I64d\n",ans);

     }

     return ;

 }

 //容斥原理

 #include <stdio.h>

 #include <string.h>

 #include <math.h>

 typedef __int64 LL;

 const int Mod=;

 const int maxn=;

 bool flag[maxn];

 int prime[maxn],num,n;

 int factor[],cnt;

 bool vis[];

 LL ans,temp;

 void get_prime()

 {

     num=;memset(flag,true,sizeof(flag));

     for(int i=;i<maxn;i++)

     {

         if(flag[i]) prime[num++]=i;

         for(int j=;j<num&&prime[j]*i<maxn;j++)

         {

             flag[i*prime[j]]=false;

             if(i%prime[j]==) break;

         }

     }

 }

 void get_factor()

 {

     cnt=;

     int i,top=(int)sqrt(n*1.0),t=n;

     for(i=;i<num && prime[i]<=top;i++)

     {

         if(t%prime[i]==)

         {

             factor[cnt++]=prime[i];

             while(t%prime[i]==)

                 t/=prime[i];

         }

     }

     if(t>) factor[cnt++]=t;

 }

 void dfs(int now,int top,int start,LL s)

 {

     if(now==top)

     {

         LL t=(n-)/s;

         LL a=((t+)*t/)%Mod;

         LL b=(a*s)%Mod;

         temp=(temp+b)%Mod;

         return ;

     }

     for(int j=start;j<cnt;j++)

     {

         if(!vis[j])

         {

             vis[j]=true;

             dfs(now+,top,j+,s*factor[j]);

             vis[j]=false;

         }

     }

     return ;

 }

 void solve()

 {

     ans=;

     int c=;

     for(int i=;i<=cnt;i++)

     {

         memset(vis,false,sizeof(vis));

         temp=;dfs(,i,,);

         ans=(((ans+c*temp)%Mod)+Mod)%Mod;

         c=-c;

     }

 }

 int main()

 {

     get_prime();

     while(scanf("%d",&n),n)

     {

         get_factor();

         solve();

         printf("%I64d\n",ans);

     }

     return ;

 }

巴特西

hdu 3501 容斥原理或欧拉函数

Calculation 2

最新文章

热门文章