目錄：
- 題目：
- 分析：
- 代碼：
題目：
單擊檢視題目
分析：
【算法分析與設計】
通過簡單觀察可以發現，每次畫出向量（n，i）經過的格點個數為gcd(i，n)，那麼答案就等于
直接求解的時間複雜度是O(n)的。
那麼
，其中d為n的約數。fai(n)表示1～n中與n互質的數的個數。通過這樣的變形，我們就可以得到時間複雜度為 O(C∗sqrt(n)) O ( C ∗ s q r t ( n ) ) 的算法，C為n的約數個數。
代碼：
#pragma GCC optimize("3")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#define LL long long
using namespace std;
inline LL read() {
LL d=,f=;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-;s=getchar();}
while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
return d*f;
}
LL phi(LL x)
{
LL k=x;
LL i=;
while(x>)
{
if(x%i==)
{
k-=k/i;
while(x%i==) x/=i;
}
i++;
}
return k;
}
LL ans=;
int main()
{
// freopen("beats.in","r",stdin);
// freopen("beats.out","w",stdout);
LL n=read();
for(LL i=;i<=trunc(sqrt(n));i++)
{
if(n%i==)
{
LL k=i;
ans+=k*phi(n/k);
if(n/k!=k)
{
k=n/i;
ans+=k*phi(n/k);
}
}
}
printf("%lld",ans+);
fclose(stdin);
fclose(stdout);
return ;
}