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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define maxn 4000005using namespace std;int zs[maxn/4],t=0,low[maxn+5];ll f[maxn+5],n,T;bool v[maxn+5];inline void init(){    f[1]=1,low[1]=1;    for(int i=2;i<=maxn;i++){        if(!v[i]) zs[++t]=i,f[i]=i*2-1,low[i]=i;        for(int j=1,u;j<=t&&(u=zs[j]*i)<=maxn;j++){            v[u]=1;            if(!(i%zs[j])){                low[u]=low[i]*zs[j];                if(low[i]==i) f[u]=f[i]*zs[j]+low[i]*(zs[j]-1);                else f[u]=f[i/low[i]]*f[low[u]];                break;            }                        low[u]=zs[j];            f[u]=f[i]*(2*zs[j]-1);        }    }        for(int i=1;i<=maxn;i++) f[i]+=f[i-1];}int main(){    init();    while(scanf("%lld",&n)==1&&n) printf("%lld\n",f[n]-n*(n+1)/2);        return 0;}