[BZOJ2705][SDOI2012]Longge的问题 数学

时间:2022-02-16 18:41:05

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2705

首先分析得题目所求$gcd(i,N)$的取值只可能是$N$的因子,则有$$Ans=\sum_{d|N}d\sum_{i=1}^N[gcd(i,N)==d]$$

$$Ans=\sum_{d|N}d\sum_{i=1}^{\frac{N}{d}}[gcd(i,\frac{N}{d})==1]$$

$$Ans=\sum_{d|N}dφ(\frac{N}{d})$$

我们可以枚举$N$的因子,然后用$O(\sqrt{N})$的时间求φ。

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll N;
ll Phi(ll x){
int M=floor(sqrt(x));
ll ret=x;
for(int i=;i<=M;i++){
if(x%i==){
ret=ret/i*(i-);
while(x%i==) x/=i;
}
}
if(x>) ret=ret/x*(x-);
return ret;
}
int main(){
scanf("%lld",&N);
int M=floor(sqrt(N));
ll Ans=;
for(int i=;i<=M;i++){
if(N%i==){
Ans+=Phi(N/i)*i;
if((ll)i*i<N) Ans+=Phi(i)*(N/i);
}
}
printf("%lld\n",Ans);
return ;
}