题解：CF1717E Madoka and The Best University
看到题目，有三个变量，首先想到消参。由辗转相减法可知 $\gcd (a,b) = \gcd (a,a + b)$，又因为 $a + b + c = n$，所以 $a + b = n - c$，即 $\gcd (a,b) = \gcd (a,n - c)$。
令 $g = \gcd (a,n - c)$，将题目所求进行转化，则有 $\sum \mathrm{lcm} (c,\gcd (a,b)) = \sum \mathrm{lcm} (c,\gcd (a,n - c))$。枚举 $c,g$，不难发现答案与 $a$ 的大小无直接联系，只与符合条件的 $a$ 的个数有关。由 $\gcd$ 的定义可知，$\gcd (\frac{a}{g},\frac{n - c}{g}) = 1$，也就是说符合条件的 $a$ 满足 $\frac{a}{g}\perp\frac{n - c}{g}$，不难想到欧拉函数 $\varphi(x)$ 表示与 $x$ 互质的数的个数。于是答案就变为 $\sum \limits_{g \mid n - c}\mathrm{lcm} (c,g) \times \varphi(\frac{n - c}{g})$，预处理欧拉函数便可解决问题。
但是在编写代码的时候还需要注意一些细节，$a,b,c$ 都是正整数，所以枚举的时候 $c \in [1,n - 2]$，枚举因数的时候要满足 $a < n - c = a + b$，所以 $a = 1$ 的时候 $\frac{n - c}{a}$ 应该舍去。
代码如下：
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,cnt,ans,p[MAX],phi[MAX],flag[MAX];
int gcd (int x,int y) {return (!y) ? x : gcd (y,x % y);}
int main ()
{
n = read ();
phi[1] = 1;
for (int i = 2;i <= n;++i)
{
if (!flag[i]) p[++cnt] = i,phi[i] = i - 1;
for (int j = 1;j <= cnt;++j)
{
if (i * p[j] > n) break;
flag[i * p[j]] = 1;
if (i % p[j] == 0)
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
phi[i * p[j]] = phi[i] * (p[j] - 1);
}
}
for (int i = 1;i <= n - 2;++i)
{
int k = n - i;
for (int j = 1;j * j <= k;++j)
{
if (k % j != 0) continue;
ans += 1ll * i * j / gcd (i,j) * phi[k / j] % MOD;
ans %= MOD;
if (j != 1 && k / j != j) ans += 1ll * i * k / j / gcd (i,k / j) * phi[j] % MOD,ans %= MOD;
}
}
printf ("%d\n",ans);
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
