把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

牛客229749 LCMs
题目大意：给一个序列（1e5），数字范围1e6，求每对数的LCM之和。

解：

众所周知，lcm(a,b)=a*b/gcd(a,b)，而gcd可以反演，1e6刚好支持类埃筛筛法，于是这题轻松地可以转化为对于1e6内的每个d，求得∑bc，其中b和c是d的倍数。
一旦转化成这一步，很容易就能想到能不能使用前缀和来实现，但这样的话要去记录对于每个d的倍数有哪些，空间上不支持，时间上也不支持，但是仅仅是求数对和的话，其实不一定需要记录这么多东西吧。
于是这里顺带地推出来一个简单地求数对和的方法，虽然可能仅仅适用于这题：首先记录每个数字出现的个数，然后对于每个d，记录下sum(d)和mul(d)，分别是前缀和和数对和，对于每个d，遍历其倍数，每遍历到一个数字a，就在数对和里加上它造成的值，具体的算法可以手推得到为a(cnt[a]sum(d)+cnt[a](cnt[a]-1)/2)，别忘了每步都要去取模。
这样的做法由于将对每个数添加到其因数到对每个因数寻找其倍数，复杂度降低到了埃筛复杂度，同时求得了f(1-n)。
之后就是利用f(1-n)反演得到g(1-n)，答案就为∑g(i)/i了。
本题虽然也很简单，但是涉及到多次转换，勉强算是个能打的题目。

代码

代码
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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 200005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
using namespace std;
bool is_prime[1000001] = { 1,1 };
ll prime[1000001];
ll mu[1000001];
int getmu(int n) {
	mu[1] = 1;
	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		if (!is_prime[i]) {
			prime[++cnt] = i;
			mu[i] = -1;
		}
		for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
			is_prime[i * prime[j]] = 1;
			if (i % prime[j] == 0) { mu[i * prime[j]] = 0; break; }
			else mu[i * prime[j]] = -mu[i];
		}
	}
	return cnt;
}
ll sum[1000005], mul[1000005];
ll cnt[1000005],ans[1000005];
ll cpow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % mdl;
		x = (x * x) % mdl;
		n >>= 1;
	}
	return ans;
}
int main() {
	cfast;
//	cout << "okinit";
	getmu(1000000);
	int n;
	cin >> n;
	inc(i, 0, n) {
		ll a;
		cin >> a;
		cnt[a]++;
	}
	inc(i, 1, 1000001) {
		for (int j = i; j <= 1000000; j += i) {
			if (cnt[j] != 0) {
				mul[i] += j * (cnt[j] * sum[i] %mdl+ cnt[j] * (cnt[j] - 1) / 2%mdl*j%mdl) % mdl;
			}
			sum[i] += cnt[j] * j;
			sum[i] %= mdl;
		}
	//	if (mul[i] != 0)cout << "mul." << i << " = " << mul[i] << endl;
	}
	ll ss = 0;
	inc(i, 1, 1000001) {
		for (int j = i; j <= 1000000; j += i) {
			ans[i] += mu[j/i] * mul[j] % mdl;
			ans[i] %= mdl;
		}
		ans[i] *= cpow(i, mdl - 2);
		ans[i] %= mdl;
	//	if(ans[i]!=0)cout << "ans." << i << " = " << ans[i] << endl;
		ss += ans[i];
		ss %= mdl;
	}
	cout << ss << endl;
}
/*

*/