Calculation 2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6114 Accepted Submission(s): 2499
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
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; }