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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vp;
const int inf = 1e9;
const ll INF = 1e18;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mem(a) memset(a, 0, sizeof(a))
#define PA puts("pass")
#define lowbit(x) (x & -x)
const int mod = 1e9 + 7;
const int maxn = 3e6;
const int inv = 166666668;
vi prime;
bool vis[maxn];
int phi[maxn];
void (int &x, int y){
x += y;
if(x >= mod) x -= mod;
}
void sub(int &x, int y){
x -= y;
if(x < 0) x += mod;
}
void init(){
phi[1] = 1;
for(int i = 2; i < maxn; i++){
if(!vis[i]) prime.pb(i), phi[i] = i - 1;
for(int j = 0; j < prime.size() && i * prime[j] < maxn; j++){
vis[i * prime[j]] = 1;
if(i % prime[j] == 0){
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
for (int i = 1; i < maxn; ++i) {
add(phi[i],(1ll * (i - 1) * phi[i] + phi[i - 1]) % mod);
}
}
struct HASH {
static const int mod = 12000005;
int hs[mod], head[mod], nxt[mod], id[mod], top;
void init(){
memset(head, -1, sizeof(head));
top = 1;
};
void insert(int x, int y) {
int k = x % mod;
hs[top] = x, id[top] = y, nxt[top] = head[k], head[k] = top++;
}
int find(int x) {
int k = x % mod;
for (int i = head[k]; i != -1; i = nxt[i]) if (hs[i] == x) return id[i];
return -1;
}
}mp;
int n;
int getans(int x){
if(x < maxn) return phi[x];
int t = mp.find(x);
if(t != -1) return t;
int res = 1ll * x * (x + 1) % mod * (2 * x + 1) % mod * inv % mod;
for(int l = 2, r; l <= x; l = r + 1){
r = x / (x / l);
sub(res, 1ll * (r - l + 1) * (r + l) / 2 % mod * getans(x / l) % mod);
}
mp.insert(x, res);
return res;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
cin >> n;
mp.init();
cout << 1 << 'n' << getans(n) << 'n';
return 0;
}
|
近期评论