首页 > 代码库 > 最大公约数之和——极限版II

最大公约数之和——极限版II

2024-09-11 23:18:01   240人阅读

P1490 - 【UVa11426 】最大公约数之和——极限版II

Description

技术分享

Input

输入包含至多100组数据。每组数据占一行，包含正整数N(2＜=N＜=1＜N＜4000000)。输入以N=0结束。

Output

对于每组数据，输出一行，即所对应的G值。答案保证在64位带符号整数范围内。

Sample Input

10
100
200000
0

Sample Output

67
13015
143295493160

Hint

数据范围：
对于30%的数据，2＜=N＜=2000
对于100%的数据，2＜=N＜=4000000

 

 

<style>pre.cjk { font-family: "Droid Sans Fallback", monospace } p { margin-bottom: 0.25cm; line-height: 120% } a:link { }</style> 
首先有一个公式：∑gcd(i,
N)(1<=i<=N)＝＝∑
i
× φ(N/i)
证明：设gcd(i,N)=k,∴gcd(i/k,N/k)=1，所以就要求出i/k的个数，这就是欧拉函数啊，
然后总答案就是每个约数的个数＊数值。
其实这样可以过了，但还有更优的做法：
把式子变形成：sigma
d=1,d<=n,d*sigma,i=2,n/d φ(i)。
然后就搞个前缀和优化，然后用数论分块。
因为有一大段区间的sigma的值是一样的，右端点r=n/(n/l),左端点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 }


 


 






最大公约数之和——极限版II






























        

            
                
                  
                
                

                    联系

                    我们