HDU3501 Calculation 2 [欧拉函数]

  题目传送门


  

Calculation 2

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6114    Accepted Submission(s): 2499


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$,求小于$N$且与$N$不互质的正整数之和,对$1000000007$取模。   容易想到,直接求肯定不好做,所以转化为求$1$到$N-1$与小于$N$且与$N$互质的正整数之和的差。   求$\sum_i=1^{N-1}$需要用到这个定理:   令$s$为$N-1$与小于$N$且与$N$互质的正整数之和,则$s=\phi(N)*N/2$。   证明如下:   首先明确:如果$gcd(n,x)=1,n>x$,则$gcd(n,n-x)=1$,由减法原理易证。   那么令$N-1$与小于$N$且与$N$互质的正整数集合为$a[]$。那么   $s=a[0]+a[1]+a[2]+...+a[\phi(n)]$   可转化为   $s=(n-a[0])+(n-a[1])+(n-a[2])+...+(n-a[\phi(n)])$   (因为$a[]$中元素是不重复的,所以$n-a[i]$也是不重复的,且与$a[]$中的元素一一对应。)   再将两式相加可得   $2*s=n*\phi(n)$即$s=\phi(n)*n/$   那么这道题就好做了,求欧拉函数然后代公式就完事了。   Code:
//It is made by HolseLee on 18th Jul 2019
//HDU 3501
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;

typedef long long ll;
ll n,ans;

inline ll get(ll x)
{
    ll ret=n, y=x;
    for(ll i=2; i*i<=y; ++i) {
        if( !(y%i) ) {
            ret=ret*(i-1)/i;
            while( !(y%i) ) y/=i;
        }
    }
    if( y!=1 ) ret=ret*(y-1)/y;
    return (ret*n/2)%mod;
}

int main()
{
    while( 1 ) {
        scanf("%lld",&n);
        if( !n ) break;
        ans=((n-1)*n/2)%mod;
        ans=(ans-get(n)+mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

 

 

上一篇:性能指标


下一篇:【分类模型评判指标 一】混淆矩阵(Confusion Matrix)