题目链接：
http://acm.hust.edu.cn/vjudge/contest/70017#problem/O
题意：
给定一个正整数N(N<4000000)， 求G=∑i=1i<N∑j=i+1j≤Ngcd(i,j)的值
分析
已知f(N)=gcd(1,N)+gcd(2,N)+⋯+gcd(N−1,N)
即j=N,f(N)=∑i=1i<Ngcd(i,N)
则结果为f(2)+f(3)+f(4)+⋯+f(N)
即ans=∑i=2i≤Nf(i)
根据gcd性质，若gcd(k,n)=i,则必有gcd(k/i,n/i)=1，即k/i与n/i互质，
那么枚举i的值，$ f(n)等于N/i$的欧拉函数值的和
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#define MOD 1000000007
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
/*---------------------------head files----------------------------------*/
const int maxn = 4000009 ;
int phi[maxn], prime[maxn / 10];
long long s[maxn],f[maxn];
int tot ;
bool not_prime[maxn];
void init()
{
int i, j;
phi[1] = 1;
for ( int i = 2; i <= 4000000 ; i ++ )
{
if ( !not_prime[i] )
{
phi[i] = i - 1;
prime[++tot] = i;
}
{
for ( j = 1; j <= tot && i * prime[j] <= 4000000; j++ )
{
not_prime[i * prime[j]] = 1;
if ( i % prime[j] == 0 )
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
{
phi[i * prime[j]] = phi[i] * ( prime[j] - 1 );
}
}
}
//for ( i = 1; i <= 4000000; i++ ) sum[i] = ( sum[i - 1] + phi[i] ) % mod;
}
}
//预处理素数与欧拉函数值
int main()
{
init();
for (int i = 2 ; i < maxn ; i ++)
{
for (int j = 1 ; j * i <maxn ; j ++ )
{
f[j*i] += phi[i]*j;
}
}
for (int i = 2 ; i < maxn ; i ++)
{
s[i] = s[i-1] + f[i];
}
int n;
while (~scanf("%d",&n)&&n)
{
printf("%lld\n",s[n]);
}
}
|