UVA GCD - Extreme (II)

discription

Given the value of N, you will have to find the value of G. The definition of G is given below:
Here GCD(i, j) means the greatest common divisor of integer i and integer j.
For those who have trouble understanding summation notation, the meaning of G is given in the
following code:
G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
G+=gcd(i,j);
}
/*Here gcd() is a function that finds
the greatest common divisor of the two
input numbers*/
Input
The input file contains at most 100 lines of inputs. Each line contains an integer N (1 < N < 4000001).
The meaning of N is given in the problem statement. Input is terminated by a line containing a single
zero.
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.
Sample Input
10
100
200000
0
Sample Output
67
13015
143295493160

貌似是蓝书上有的一道题，当时刘汝佳是用 N log N 的筛法筛的，但是我们如果把积性函数推出来的话，可以

把那个log也去掉，做到O(N)预处理，O(1)查询。

大概最后就是推这么个积性函数： f(T)=Σφ(d)*(T/d) ,其中d|T

优化了一个log之后艹爆了时限hhh

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#define ll long long

#define maxn 4000005

using namespace std;

int zs[maxn/],t=,low[maxn+];

ll f[maxn+],n,T;

bool v[maxn+];

inline void init(){

    f[]=,low[]=;

    for(int i=;i<=maxn;i++){

        if(!v[i]) zs[++t]=i,f[i]=i*-,low[i]=i;

        for(int j=,u;j<=t&&(u=zs[j]*i)<=maxn;j++){

            v[u]=;

            if(!(i%zs[j])){

                low[u]=low[i]*zs[j];

                if(low[i]==i) f[u]=f[i]*zs[j]+low[i]*(zs[j]-);

                else f[u]=f[i/low[i]]*f[low[u]];

                break;

            }

            low[u]=zs[j];

            f[u]=f[i]*(*zs[j]-);

        }

    }

    for(int i=;i<=maxn;i++) f[i]+=f[i-];

}

int main(){

    init();

    while(scanf("%lld",&n)==&&n) printf("%lld\n",f[n]-n*(n+)/);

    return ;

}

巴特西

UVA GCD - Extreme (II)

最新文章

热门文章