首页 > 代码库 > spoj 3871. GCD Extreme 欧拉+积性函数
spoj 3871. GCD Extreme 欧拉+积性函数
3871. GCD ExtremeProblem code: GCDEX |
Given the value of N, you will have to find the value of G. The meaning of G is given in the following code
G=0;
for(k=i;k< N;k++)
for(j=i+1;j<=N;j++)
{
G+=gcd(k,j);
}
/*Here gcd() is a function that finds the greatest common divisor of the two input numbers*/
Input
The input file contains at most 20000 lines of inputs. Each line contains an integer N (1<n<1000001). the="" meaning="" of="" n="" is="" given="" in="" problem="" statement.="" input="" terminated="" by="" a="" line="" containing="" single="" zero.="" <h3="">Output
For each line of input produce one line of output. This line contains the value of G for the corresponding N. The value of G will fit in a 64-bit signed integer.
Example
Input:101002000000Output:6713015143295493160
题意:
G=0;
for(k=i;k< N;k++)
for(j=i+1;j<=N;j++)
{
G+=gcd(k,j);
}
思路: G[n] = sigma( d|n phi[d]*(n/d) ); 这个能求出S[n]的值,累加求和就行。
关键在于G[n]函数能用筛选来做,因为是积性函数。
两种筛选方法,一种TLE,一种ac。
超时代码:
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 typedef long long LL; 7 8 const int maxn = 1000000+3; 9 LL G[maxn];10 int opl[maxn];11 void init()12 {13 LL i,j;14 for(i=2;i<maxn;i++) opl[i] = i;15 for(i=2;i<maxn;i++)16 {17 if(opl[i]==i)18 {19 for(j=i;j<maxn;j=j+i)20 opl[j]=opl[j]/i*(i-1);21 }22 for(j=1;i*j<maxn;j++)23 G[j*i] = G[j*i] + opl[i]*j;24 }25 for(i=3;i<maxn;i++)26 G[i] +=G[i-1];27 }28 int main()29 {30 init();31 int T,n;32 while(scanf("%d",&n)>0)33 {34 printf("%lld\n",G[n]);35 }36 return 0;37 }
AC代码:
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 typedef long long LL; 7 8 const int maxn = 1e6+3; 9 int phi[maxn];10 LL g[maxn];11 void init()12 {13 for(int i=1;i<maxn;i++) phi[i] = i;14 for(int i=2;i<maxn;i++)15 {16 if(phi[i]==i) phi[i] = i-1;17 else continue;18 for(int j=i+i;j<maxn;j=j+i)19 phi[j] = phi[j]/i*(i-1);20 }21 for(int i=1;i<maxn;i++) g[i] = phi[i];22 for(int i=2;i<=1000;i++)23 {24 for(LL j=i*i,k=i;j<maxn;j=j+i,k++)25 if(i!=k)26 g[j] = g[j] + phi[i]*k + phi[k]*i;27 else g[j] = g[j] + phi[i]*k;28 }29 g[1] = 0;30 for(int i=2;i<maxn;i++) g[i] = g[i]+g[i-1];31 }32 int main()33 {34 init();35 int T,n;36 scanf("%d",&T);37 while(T--)38 {39 scanf("%d",&n);40 printf("%lld\n",g[n]);41 }42 return 0;43 }
spoj 3871. GCD Extreme 欧拉+积性函数