Problem H
GCD Extreme
Input: Standard Input
Output: Standard Output
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); } |
Input
The input file contains at most 20000 lines of inputs. Each line contains an integer N (1<N<200001). 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 Output for Sample Input
10 100 20000 | 67 13015 1153104356 |
Problemsetter: Shahriar Manzoor and Syed Monowar Hossain
Special Thanks: Shahriar Manzoor and Syed Monowar Hossain
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int phi[1000100];
long long a[1000100];
void phi_table(int n )//筛选法求欧拉函数
{
for(int i=2 ; i<= n; i++) phi[i] = 0;
phi[1]= 1;
for(int i =2; i<=n ;i ++)
if(!phi[i])
for(int j = i ; j<=n; j+=i)
{
if(!phi[j]) phi[j] = j;
phi[j] = phi[j] /i*(i-1);
}
}
void gcd_sum(int n)//求sigema gcd(i,n);(1<=i<=n-1);不包括n
{
for(int i=2;i<n;i++) a[i]=phi[i];//
double k=sqrt(0.5+n);
for(int i=2;i<=k;i++)
{
for(int j=i,bit=1;j<n;j+=i,bit++)
{
if(i<bit) a[j]+=phi[bit]*i+phi[i]*bit;
else if(i==bit) a[j]+=phi[i]*i;
}
}
}
void gcd_sum_again(int n)
{
for(int i=1;i<n;i++) a[i]+=a[i-1];//二维的,要求和
}
int main()
{
phi_table(1000100);
gcd_sum(1000100);
gcd_sum_again(1000100);
int n;
while(cin>>n&&n)
{
cout<<a[n]<<endl;
}
return 0;
}