[jzoj 3509]【NOIP2013模擬11.5B組】倒黴的小C {尤拉函式 數論 歐幾里得演算法}

NO IMAGE

題目

Description
小G最近迷上了島國動漫《Angel Beats》,她為了畫出一個更霸氣的Angel Beats的logo,想了如下辦法:
從(0,0)開始,畫到(n,1),再從(n,1),畫到(2*n,-1),再到(3*n,2),再到(4*n,-2),依此類推,即每次畫出一個(n,(-1)^(i 1)*i)的向量,一共畫出n個這樣的向量。現在小G想讓小C求出這個圖形穿過了多少格點(座標都是整數)。
由於小C想要認真地聽他的數學課並且想自己在接力賽中因RP暴光而發生接力棒傳錯這類的糗事,所以這個問題就交給你啦。小G說,如果連你也解決不好,就把你的RP也吸光。
Input
輸入檔案中僅一行為一個整數n。
Output
輸出檔案中僅一行為一個數,表示穿過的格點數。

題目大意

求∑i=1ngcd(i,n)” role=”presentation”>∑ni=1gcd(i,n)∑i=1ngcd(i,n)\sum_{i=1}^{n}gcd(i,n)


解題思路

通過簡單觀察可以發現,每次畫出向量(n,i)經過的格點個數為gcd(i,n),那麼答案就等於

Ans=1 ∑i=1ngcd(i,n)” role=”presentation”>Ans=1 ∑i=1ngcd(i,n)Ans=1 ∑i=1ngcd(i,n)

Ans=1 \sum_{i=1}^{n}gcd(i,n)。直接求解的時間複雜度是O(n)的。那麼

Ans=1 ∑d|nd∗φ(n/d)” role=”presentation”>Ans=1 ∑d|nd∗φ(n/d)Ans=1 ∑d|nd∗φ(n/d)

Ans=1 \sum_{d|n}d*\varphi (n/d),其中d為n的約數。fai(n)表示1~n中與n互質的數的個數。通過這樣的變形,我們就可以得到時間複雜度為O(C*sqrt(n))的演算法,C為n的約數個數。

以下轉載至(https://blog.csdn.net/OIerLH/article/details/59134485):

設有一個n乘m的矩陣,設左上角為(0,0),若對角線穿過格點p(x,y),則以a(x,0),b(0,0),p(x,y)為頂點的三角形與a1(0,0),b1(n,0),c1(n,m)構成的三角形相似,因此n/x=m/y,而多個這種三角形沿著對角線分佈,就會有n/x個,總個數則為最小x的貢獻,而要使x最小,n/x必須最大且滿足n/x能整除m,所以答案即為gcd(n,m)
相信最令人懵逼的不是O(n)方法,而是後面的那條奇奇怪怪的等價公式,即ans=1 Σgcd(i,n)等價於ans=1 Σ(d|n)d*φ(n/d),以下給出證明:
其實公式2是表示gcd(i,n)為d的i的個數等於φ(n/d)表示小於n/d的數中與n/d互質的數的個數。設x為小於n/d的與n/d互質的數,則gcd(x*d,n)一定為d,因為gcd(i,n)一定為d或n/d的因子,而若gcd(i,n)不為d,則一定存在d1|n且d1>d,那麼這個d1至少有一個n/d的因子,而x與n/d互質,所以gcd(n,x*d)一定為d,所以ans=1 Σgcd(i,n)等價於ans=1 Σ(d|n)d*φ(n/d)


程式碼

#include<cstdio> 
#include<algorithm>
#include<cmath>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std; 
long long  n,anss;  
long long phi(long long n) //尤拉函式(求1到x與x互質的數的個數)
{
long long ans=n; 
for (long long i=2;i<=sqrt(n);i  )
if (n%i==0){
ans=ans/i*(i-1); 
while (n%i==0) n/=i; 
}
if (n>1) ans=ans/n*(n-1); 
return ans; 
}
int main()
{
//  fre(beats); 
scanf("%lld",&n); 
for (long long i=1;i<=trunc(sqrt(n));i  )
if (n%i==0) {
long long k=i; 
anss =k*phi(n/k); 
if (k!=n/k)
{
k=n/i;
anss =k*phi(n/k); 
}
}
printf("%lld",anss 1); 
}