P1490 - 【UVa11426 】最大公約數(shù)之和——極限版II

Description

Input

輸入包含至多100組數(shù)據(jù)。每組數(shù)據(jù)占一行，包含正整數(shù)N(2＜=N＜=1＜N＜4000000)。輸入以N=0結(jié)束。

Output

對于每組數(shù)據(jù)，輸出一行，即所對應(yīng)的G值。答案保證在64位帶符號整數(shù)范圍內(nèi)。

Sample Input

10
100
200000
0

Sample Output

67
13015
143295493160

Hint

數(shù)據(jù)范圍：
對于30%的數(shù)據(jù)，2＜=N＜=2000
對于100%的數(shù)據(jù)，2＜=N＜=4000000

?

?

首先有一個公式：∑gcd(i,N)(1<=i<=N)==∑i×φ(N/i) 證明：設(shè)gcd(i,N)=k,∴gcd(i/k,N/k)=1，所以就要求出i/k的個數(shù)，這就是歐拉函數(shù)啊，
然后總答案就是每個約數(shù)的個數(shù)＊數(shù)值。 其實(shí)這樣可以過了，但還有更優(yōu)的做法： 把式子變形成：sigma d=1,d<=n,d*sigma,i=2,n/d φ(i)。
然后就搞個前綴和優(yōu)化，然后用數(shù)論分塊。 因?yàn)橛幸淮蠖螀^(qū)間的sigma的值是一樣的，右端點(diǎn)r=n/(n/l),左端點(diǎn)l=r+1。
1 #include<set> 2 #include<map> 3 #include<queue> 4 #include<stack> 5 #include<ctime> 6 #include<cmath> 7 #include<string> 8 #include<vector> 9 #include<cstdio> 10 #include<cstdlib> 11 #include<cstring> 12 #include<iostream> 13 #include<algorithm> 14 #define LL long long 15 #define maxn 4000010 16 #define RG register 17 using namespace std; 18 bool bj[maxn]; 19 int su[maxn],phi[maxn],n; 20 LL s[maxn]; 21 inline void getphi(){ 22 phi[1]=1;int sum=0; 23 for(RG int i=2;i<=maxn;i++){ 24 if(!bj[i]) su[++sum]=i,phi[i]=i-1; 25 for(RG int j=1;j<=sum;j++){ 26 if(su[j]*i>maxn) break; 27 bj[su[j]*i]=1; 28 if(i%su[j]==0){ 29 phi[i*su[j]]=phi[i]*su[j]; 30 break; 31 } 32 else phi[i*su[j]]=phi[i]*(su[j]-1); 33 } 34 } 35 } 36 int main() 37 { 38 freopen("!.in","r",stdin); 39 freopen("!.out","w",stdout); 40 getphi(); 41 for(RG int i=2;i<=maxn-10;i++) 42 s[i]=s[i-1]+phi[i]; 43 while(1){ 44 scanf("%d",&n); 45 if(n==0) break; 46 LL ans=0; 47 for(LL l=1,r;l<=n;l=r+1) 48 r=n/(n/l),ans+=(l+r)*(r-l+1)*s[n/l]/2; 49 printf("%lld\n",ans); 50 } 51 return 0; 52 }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/pantakill/p/6657822.html

總結(jié)

以上是生活随笔為你收集整理的最大公约数之和——极限版II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。