首先我们了解一下欧拉函数phi[x],phi[x]表示的是不超过x且和x互素的整数个数
phi[x]=n*(1-1/p1)*(1-1/p2)....(1-1/pn);
计算欧拉函数的代码为
int euler_phi(int n){
int m=(int)sqrt(n+0.5);
int ans=n;
for(int i=;i*i<=m;i++){
if(n%i==){//
ans=ans/i*(i-);
while(n%i==)n=n/;
}
}
if(n>)ans=ans/n*(n-);
return ans;
}
也可以通过类似于素数打表的方法来对欧拉函数进行打表
void phi_table(int n){
for(int i=;i<=n;i++)phi[i]=;
phi[]=;
for(int i=;i<=n;i++){
if(phi[i]==)
for(int j=i;j<=n;j=j+i){
if(phi[j]==)phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
}
}
题意
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
设f(n)=gcd(1,2)+gcd(1,3)+gcd(2,3)+....+gcd(n-1,n); 题意是求1<=i<j<=n的数对（i,j）所对应的gcd(i,j)的和s(j)
s(n)=f(1)+f(2)+f(3)+f(4)+....f(n);
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<cstdlib>
#include<string>
#define eps 0.000000001
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
const int N=+;
ll S[N],f[N];
ll phi[N];
ll euler_phi(int n){
int m=(int)sqrt(n+0.5);
ll ans=n;
for(int i=;i*i<=m;i++){
if(n%i==){//2一定是素因子
ans=ans/i*(i-);
while(n%i==)n=n/;
}
}
if(n>)ans=ans/n*(n-);
return ans;
}
void phi_table(int n){
for(int i=;i<=n;i++)phi[i]=;
phi[]=;
for(int i=;i<=n;i++){
if(phi[i]==)
for(int j=i;j<=n;j=j+i){
if(phi[j]==)phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
}
}
void init(){
int n=N;
phi_table(N);
memset(f,,sizeof(f));
for(int i=;i<=n;i++){
for(int j=i*;j<=n;j=j+i)f[j]=f[j]+i*phi[j/i];
}
memset(S,,sizeof(S));
S[]=f[];
for(int i=;i<=n;i++)S[i]=S[i-]+f[i];
}
int main(){
int n;
init();
while(scanf("%d",&n)!=EOF){
//init(n);
if(n==)break;
printf("%lld\n",S[n]);
}
}