题目
求
∑
x
=
1
n
−
1
[
gcd
(
x
,
n
)
=
1
]
⋅
x
\sum_{x=1}^{n-1}\big[\gcd(x,n)=1\big]\cdot x
x=1∑n−1[gcd(x,n)=1]⋅x
思路
根据
gcd
(
a
,
b
)
=
gcd
(
a
−
b
,
b
)
\gcd(a,b)=\gcd(a-b,b)
gcd(a,b)=gcd(a−b,b) 可知：
gcd
(
n
,
x
)
=
gcd
(
n
−
x
,
x
)
\gcd(n,x)=\gcd(n-x,x)
gcd(n,x)=gcd(n−x,x)
以及
gcd
(
n
,
n
−
x
)
=
gcd
(
x
,
n
−
x
)
\gcd(n,n-x)=\gcd(x,n-x)
gcd(n,n−x)=gcd(x,n−x)
所以说
gcd
(
n
,
x
)
=
gcd
(
n
,
n
−
x
)
\gcd(n,x)=\gcd(n,n-x)
gcd(n,x)=gcd(n,n−x) 。若二者都为
1
1
1 ，则提供一份
(
n
−
x
)
+
(
x
)
=
n
(n-x)+(x)=n
(n−x)+(x)=n 的贡献；若都不为
1
1
1 ，无话可说。
所以只需要找到有多少组即可。这是
φ
\varphi
φ 的范畴了。
代码
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std
;
typedef long long int_
;
inline int readint(){
int a
= 0; char c
= getchar(), f
= 1;
for(; c
<'0'||c
>'9'; c
=getchar())
if(c
== '-') f
= -f
;
for(; '0'<=c
&&c
<='9'; c
=getchar())
a
= (a
<<3)+(a
<<1)+(c
^48);
return a
*f
;
}
int getphi(int n
){
int res
= n
;
for(int i
=2; 1ll*i
*i
<=n
; ++i
)
if(n
%i
== 0){
res
-= res
/i
;
while(!(n
%i
)) n
/= i
;
}
if(n
> 1) res
-= res
/n
;
return res
;
}
int main(){
int n
; const int Mod
= 1e9+7;
while(~scanf("%d",&n
) && n
){
long long sy
= n
-getphi(n
)-(n
!=1);
sy
= (sy
>>1)*n
+(sy
&1)*(n
>>1);
printf("%lld\n",sy
%Mod
);
}
return 0;
}
