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
97
98
99
100
101
|
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 maxn = 5e6 + 5;
ll n;
unordered_map<ll, int> ansphi, ansmu;
int phi[maxn];
vi prime;
bool vis[maxn];
int mu[maxn];
const int mod = 998244353;
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(){
mu[1] = phi[1] = 1;
for(int i = 2; i < maxn; i++){
if(!vis[i]) prime.eb(i), phi[i] = i - 1, mu[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]];
mu[i * prime[j]] = -mu[i];
}
}
for (int i = 1; i < maxn; ++i) {
add(phi[i], phi[i - 1]);
}
for(int i = 1; i < maxn; i++){
mu[i] += mu[i - 1];
if(mu[i] >= mod) mu[i] -= mod;
if(mu[i] < 0) mu[i] += mod;
}
}
int getmu(ll x){
if(x < maxn) return mu[x];
if(ansmu[x]) return ansmu[x];
int ret = 1;
for(ll l = 2, r; l <= x; l = r + 1){
r = x / (x / l);
sub(ret, (r - l + 1) % mod * getmu(x / l) % mod);
}
return ansmu[x] = ret;
}
int getphi(ll x){
if(x < maxn) return phi[x];
if(ansphi[x]) return ansphi[x];
int ret = 0;
for(ll l = 2, r; l <= x; l = r + 1){
r = x / (x / l);
sub(ret, (r - l + 1) % mod * getphi(x / l) % mod);
}
add(ret, 1ll * (x + 1) % mod * x % mod * (mod + 1 >> 1) % mod);
return ansphi[x] = ret;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
cin >> n;
int res = 0;
for(ll l = 1, r; l <= n; l = r + 1){
r = n / (n / l);
int tmp = getphi(n / l);
add(tmp, tmp);
sub(tmp, 1);
add(res, 1ll * (getmu(r) - getmu(l - 1) + mod) % mod * tmp % mod);
}
cout << res << 'n';
return 0;
}
|
近期评论