Zth's Blog

记录学习路上的点滴

0%

cf818E. Madoka and The Best University 数学

题目链接

题目描述

给定一个$n$, 对所有满足$1 \leq a, b, c$并且$a + b + c = n$的三元组$a, b, c$求$\sum lcm(c, gcd(a, b))$

数据范围

$1 \leq n \leq 10^5$

题解

首先$\sum lcm(c, gcd(a, b)) = \sum \frac{c \times gcd(a, b)}{gcd(gcd(a, b), c)}$

然后三个变量不好看, 由于有$a + b + c = n$, 所以可以把$b$用$n - a - c$表示, 则由更相减损数得$gcd(a, b) = gcd(a, n - a - c) = gcd(a, n - c)$

原式变为$\sum \frac{c \times gcd(a, n - c)}{gcd(gcd(a, n - c), c)}$

考虑枚举$c$, 原式变为$\sum c \sum \frac{gcd(a, n - c)}{gcd(gcd(a, n - c), c)}$, 如果再枚举$a$的话时间复杂度就是$O(n^2)$的了, 肯定过不了, 所以考虑快速计算$\sum \frac{gcd(a, n - c)}{gcd((gcd(a, n - c), c)}$

然后就不会了

真正的题解

首先$\sum lcm(c, gcd(a, b))$, 这个在化简的时候根本就不用展开

考虑枚举$c$, 现在相当于$c$固定了, 设$d = gcd(a, b)$, 我们枚举$d$, 求$gcd(a, b) = d$的有序对$(a, b)$的个数这个题就做出来了, 当然这个过程的时间复杂度最高只能是$O(\sqrt n)$级别的

这就用到了我们上述推导中的$gcd(a, b) = gcd(a, n - c)$, 这说明$d$必然是$n - c$的约数, 而约数的个数恰好是根号级的

现在我们确定了$c$, 确定了$d$, 怎么求出有序对$(a, b)$的数量呢, 可以看出我们只需要求出$gcd(a, n - c) = d$的$a$的数量就可以了

$a$显然应该是$d$的倍数, 设$a = k_1 d, n - c = k_2 d$,那么既然$gcd(a, n - c) = d$, 必然有$gcd(k_1, k_2) = 1$,

这里还应该有$k_1 < k_2$, 而且在$c, d$固定的情况下$k_2$是已知的, 则实际上$k_1$的数量就是$\phi(k_2) = \phi(\frac{n - c}{d})$

这也就是$a$的数量, 也就是有序对$(a, b)$的数量

$\phi()$预处理就好了

这题不看题解我绝对想不到, 而且看了题解还得琢磨一会才能明白

代码

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
#include <iostream>
#include <cstdio>
#include <cmath>

const int mod = 1e9 + 7;

int n;
int prm[112345], cnt, phi[112345];
bool np[112345];
int ans;

int Gcd(int a, int b)
{
return b == 0 ? a : Gcd(b, a % b);
}

void Euler()
{
phi[1] = 1;

for(int i = 2; i <= n; i ++)
{
if(! np[i])
prm[++ cnt] = i, phi[i] = i - 1;

for(int j = 1; j <= cnt && i * prm[j] <= n; j ++)
{
np[i * prm[j]] = true;

if(i % prm[j] == 0)
{
phi[i * prm[j]] = phi[i] * prm[j];

break;
}
else
phi[i * prm[j]] = phi[i] * (prm[j] - 1);
}
}
}

int main()
{
scanf("%d", &n);

Euler();

for(int i = 1; i <= n - 2; i ++)
{
int sq = sqrt(n - i);

for(int j = 1; j <= sq; j ++)
{
if((n - i) % j) continue;

if(j != n - i) //d不能等于n - c, 否则有a = n - c, 这时b = 0, 不符合题意了
{
int tmp = 1LL * phi[(n - i) / j] * i * j / Gcd(i, j) % mod;

ans = (1LL * ans + tmp) % mod;
}

int x = ((n - i) / j);

if(x != j && x != n - i)
{
int tmp = 1LL * phi[(n - i) / x] * i * x / Gcd(i, x) % mod;

ans = (1LL * ans + tmp) % mod;
}
}
}

printf("%d\n", ans);

return 0;
}