【题解】51nod-1575-Gcd and Lcm

题目

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1575

题意

$S(n)=\sum_{k=1}^n \sum_{i=1}^k \sum_{j=1}^k lcm(gcd(k,i), gcd(k, j))$

题解

$$
\begin{eqnarray}
f(n) &=& \sum_{i=1}^n \sum_{j=1}^n lcm(gcd(i,n), gcd(j,n)) \
&=& \sum_{d_1|n} \sum_{d_2|n} lcm(d_1,d_2) \sum_{i=1}^{\frac n {d_1}} [i \perp \frac n {d_1}] \sum_{j=1}^{\frac n {d_2}} [j \perp \frac n {d_2}] \
&=& \sum_{i|n} \sum_{j|n} lcm(i, j) \varphi(\frac n i) \varphi(\frac n j) \
&=& \sum_{d|n} \frac 1 d \sum_{i|n} \sum_{j|n} ij \varphi(\frac n i)\varphi(\frac n j) [gcd(i,j)=d] \
&=& \sum_{d|n} \frac 1 d \sum_{i|\frac n d} \sum_{j|\frac n d}d^2ij\varphi(\frac n {id}) \varphi(\frac n {jd})[i \perp j] \
&=& \sum_{d|n} \frac n d \sum_{i|d} \sum_{j|d} ij\varphi(\frac di)\varphi(\frac dj)[i\perp j]
\end{eqnarray}
$$

$$
\begin{eqnarray}
g(d) &=& \sum_{i|d} \sum_{j|d} ij \varphi(\frac d i) \varphi(\frac d j) [i \perp j] \
h(d, k) &=&\sum_{i|\frac dk}\sum_{j|\frac dk} k^2ij \varphi(\frac d{ki})\varphi(\frac d {kj}) \
&=& k^2 (\sum_{i|\frac dk} i\varphi(\frac d {ki}))^2\
g(d) &=& \sum_{k|d}\mu(k)h(d,k) \
&=& \sum_{t|d} \mu(\frac dt)h(d,\frac dt) \
&=& \sum_{t|d}\mu(\frac dt) (\frac dt)^2(\sum_{i|t} i\varphi(\frac ti))^2 \
\end{eqnarray}
$$

$$
f=id*(\mu \cdot id_2) * (id*\varphi)^2
$$

上述推导没什么用,只需要打表就可以发现 $f$ 是一个积性函数,于是只能回归最初的梦想。
$$
\begin{eqnarray}
f(p^k) &=& \sum_{i=1}^{p^k} \sum_{j=1}^{p^k} lcm(gcd(i,n), gcd(j,n)) \
&=& \sum_{i=0}^k \sum_{j=0}^k p^{\max{i,j}} \varphi(p^{k-i}) \varphi(p^{k-j}) \
&=& \sum_{i=0}^k p^i \varphi(p^{k-i}) (2\sum_{j=0}^i \varphi(p^{k-j}) - \varphi(p^{k-i})) \
&=& p^k(2p^k-1) + \varphi(p^k) \sum_{i=0}^{k-1} (2p^k-p^{k-i-1}-p^{k-i}) \
&=& p^k(2p^k-1) + \varphi(p^k)(2kp^k - (p+1)\sum_{i=0}^{k-1} p^{k-i-1}) \
&=& \cdots \
&=& p^{k-1} + (2k+1)(p^{2k}-p^{2k-1})\
f(p) &=& 3p^2-3p+1
\end{eqnarray}
$$
可以 Min_25 筛直接搞。

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "DBG: " << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
using uLL = unsigned long long;

uLL bin(uLL x, uLL n) {
uLL ret = 1;
for (; n; n >>= 1, x = x * x)
if (n & 1) ret = ret * x;
return ret;
}
namespace min25 {
const int M = 1E6 + 100;
uLL B, N;

inline uLL pg(uLL x) { return 1; }
inline uLL ph(uLL x) { return x; }
inline uLL pq(uLL x) { return x * x; }
inline uLL psg(uLL x) { return x - 1; }
inline uLL psh(uLL x) {
return (x & 1 ? (x + 1) / 2 * x : x / 2 * (x + 1)) - 1;
}
inline uLL psq(uLL x) {
uLL a = x, b = x + 1, c = x * 2 + 1;
if (x & 1) b /= 2; else a /= 2;
if (x % 3 == 0) a /= 3;
else if (x % 3 == 1) c /= 3;
else b /= 3;
return a * b * c - 1;
}
inline uLL fpk(uLL p, uLL e, uLL pp) {
return bin(p, e - 1) + (2 * e + 1) * (bin(p, 2 * e) - bin(p, 2 * e - 1));
}
inline uLL fghq(uLL g, uLL h, uLL q) { return g - 3 * h + 3 * q; }

uLL pr[M], pc, sg[M], sh[M], sq[M];
void get_prime(uLL n) {
static bool vis[M]; pc = 0;
FOR (i, 2, n + 1) {
if (!vis[i]) {
pr[pc++] = i;
sg[pc] = sg[pc - 1] + pg(i);
sh[pc] = sh[pc - 1] + ph(i);
sq[pc] = sq[pc - 1] + pq(i);
}
FOR (j, 0, pc) {
if (pr[j] * i > n) break;
vis[pr[j] * i] = 1;
if (i % pr[j] == 0) break;
}
}
}

uLL w[M];
uLL id1[M], id2[M], h[M], g[M], q[M];
inline uLL id(uLL x) { return x <= B ? id1[x] : id2[N / x]; }

uLL go(uLL x, LL k) {
if (x <= 1 || (k >= 0 && pr[k] > x)) return 0;
uLL t = id(x);
uLL ans = fghq((g[t] - sg[k + 1]),
(h[t] - sh[k + 1]),
(q[t] - sq[k + 1]));
FOR (i, k + 1, pc) {
uLL p = pr[i];
if (p * p > x) break;
ans -= fghq(pg(p), ph(p), pq(p));
for (uLL pp = p, e = 1; pp <= x; ++e, pp = pp * p)
ans += fpk(p, e, pp) * (1 + go(x / pp, i));
}
return ans;
}

uLL solve(uLL _N) {
N = _N;
B = sqrt(N + 0.5);
get_prime(B);
uLL sz = 0;
for (uLL l = 1, v, r; l <= N; l = r + 1) {
v = N / l; r = N / v;
w[sz] = v; g[sz] = psg(v); h[sz] = psh(v); q[sz] = psq(v);
if (v <= B) id1[v] = sz; else id2[r] = sz;
sz++;
}
FOR (k, 0, pc) {
uLL p = pr[k];
FOR (i, 0, sz) {
uLL v = w[i]; if (p * p > v) break;
uLL t = id(v / p);
g[i] = (g[i] - (g[t] - sg[k]) * pg(p));
h[i] = (h[i] - (h[t] - sh[k]) * ph(p));
q[i] = (q[i] - (q[t] - sq[k]) * pq(p));

}
}
return go(N, -1) + 1;
}
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
while (T--) {
uLL n; cin >> n;
cout << min25::solve(n) % (1ull << 32)<< endl;
}
}