hdu_3501_Calculation 2

2018-06-17 21:34:06来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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.

InputFor 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.OutputFor each test case, you should print the sum module 1000000007 in a line.Sample Input

3
4
0

Sample Output

0
2

如果gcd(n,i)==1,gcd(n,n-i)==1
证:i=1(mod n)
  -i=-1(mod n)
  n-i=-1+n (mod n)
  n-i=1 (mod n)
通过欧拉函数一个数n中存在phi(n)个与之互质的数,因为i+(n-i)为n也就是有n对。
则与n互质数目之和为res=phi(n)/2*n,
ans=(n-1)*n/2-res。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define N 1000010
#define maxn 1000010
#define mod 1000000007
using namespace std;
typedef long long ll;
int p[N];
int prime[N];
int pn=0;
bool vis[N];
int main()
{
    for (int i = 2; i < N; i++) {
        if (vis[i]) continue;
        prime[pn++] = i;
        for (int j = i; j < N; j += i)
            vis[j] = 1;
    }
    ll n;
    while(~scanf("%lld",&n),n)
    {
        ll r=n;
        ll phi=n;
        for(int i=0;prime[i]*prime[i]<=r;i++)
        {
            ll tem=0;
            while(r%prime[i]==0)
            {
                r/=prime[i];
                tem++;
            }
            if(tem)
               phi=phi-phi/prime[i];
        }
        if(r!=1)
            phi-=phi/r;
        ll rem=n*phi/2;
        ll ans=n*(n-1)/2;
        printf("%lld\n",(ans-rem)%mod);
    }
}

  

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++使用htslib库读入和写出bam文件

下一篇:基于数组实现双端栈