CF1900D
从小到大排列，第\(i\)个元素作为最大值对答案的贡献为\(\sum_{x=1}^{i-1} \sum_{y=x+1}^{i-1} gcd(a_x,a_y)\)，即区间\([1,i-1]\)两两元素\(gcd\)和，记作\(val_{i-1}\)。然后考虑用第\(i\)个元素更新\(val_{i-1}\)，即\(val_i=val_{i-1}+\sum_{x=1}^{i-1}gcd(a_x,a_i)\)。处理这玩意有两种做法。
方法一
容斥。首先维护出\(cnt[j](j\le1e5)\)表示第\(i\)位之前\(j\)的倍数有多少，从大到小枚举\(a_i\)因子\(d\)，\(cnt[d]\)就是\(gcd(a_x,a_i)=d\)的个数，然后把\(d\)的因子的\(cnt\)全都减\(cnt[d]\)就筛完了，这个时间复杂度不太会证，初始化的时间复杂度肯定是调和级数，近似\(O(nlogn)\)，但是嵌套两个for枚举因子的就不太懂了（\(\sum_{i}^{n}a_i所有因子的因子数量和\)？）。
方法二
欧拉函数反演。
\[n=\sum_{d|n}\phi (d)
\\
\sum_{x=1}^{i-1}gcd(a_x,a_i)=\sum_{x=1}^{i-1}\sum_{d|gcd(a_x,a_i)}\phi (d)=\sum_{x=1}^{i-1}\sum_{d|a_i}\phi (d)[d|a_x]=\sum_{d|a_i}\phi (d)\sum_{x=1}^{i-1}[d|a_x]
\]
方法一
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define se second
#define et0 exit(0);
#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)
#define IO ios::sync_with_stdio(false),cin.tie(0);
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10, MOD = 998244353;
const long long LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7, pi = acos(-1);
int cnt[N], s[N];
vector<int> t[N];
void init() {
rep (i, 1, N - 1) {
for (int j = i; j < N; j += i) {
t[j].push_back(i);
}
}
}
void work() {
int n;
cin >> n;
rep (i, 1, N - 1) cnt[i] = 0;
vector<int> a(n + 1);
rep (i, 1, n) cin >> a[i];
sort(a.begin() + 1, a.end());
LL res = 0, sum = 0;
rep (i, 1, n) {
res += sum;
rrep (j, t[a[i]].size() - 1, 0) {
int u = t[a[i]][j];
sum += 1ll * u * cnt[u];
s[j] = cnt[u];
for (auto &x: t[u]) {
cnt[x] -= s[j];
}
}
rrep (j, t[a[i]].size() - 1, 0) {
int u = t[a[i]][j];
int v = s[j];
for (auto &x: t[u]) {
cnt[x] += s[j];
}
}
for (auto &x: t[a[i]]) {
cnt[x]++;
}
}
cout << res << "\n";
}
/*
*/
signed main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
IO
init();
int test = 1;
cin >> test;
while (test--) work();
return 0;
}
方法二
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define se second
#define et0 exit(0);
#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)
#define IO ios::sync_with_stdio(false),cin.tie(0);
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10, MOD = 998244353;
const long long LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7, pi = acos(-1);
int phi[N];
int primes[N], st[N];
int cnt[N];
vector<int> t[N];
void init() {
rep (i, 1, N - 1) {
for (int j = i; j < N; j += i) {
t[j].push_back(i);
}
}
int tot = 0;
phi[1] = 1;
for (int i = 2; i <= N - 1; i++) {
if (!st[i]) {
primes[tot++] = i;
phi[i] = i - 1;
}
for (int j = 0; primes[j] * i <= N - 1; j++) {
st[primes[j] * i] = 1;
if (i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j];
break;
} else phi[i * primes[j]] = phi[i] * (primes[j] - 1);
}
}
}
void work() {
int n;
cin >> n;
rep (i, 1, N - 1) cnt[i] = 0;
vector<int> a(n + 1);
rep (i, 1, n) cin >> a[i];
sort(a.begin() + 1, a.end());
LL res = 0, sum = 0;
rep (i, 1, n) {
res += sum;
for (auto &x: t[a[i]]) {
sum += 1ll * phi[x] * cnt[x];
cnt[x]++;
}
}
cout << res << "\n";
}
/*
*/
signed main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
IO
init();
int test = 1;
cin >> test;
while (test--) work();
return 0;
}
CF1900E
操作完成后，每个强连通分量都是完全图，强连通分量外部的的”新边“对答案没有影响。
缩完点后，\(SCC\)的”长度“为内部点数，权值为内部点权和，在这个\(DAG\)上\(dp\)即可。
自环和重边无影响，不用处理。
const int INF = 0X3f3f3f3f, N = 2e5 + 10, MOD = 998244353;
const double eps = 1e-8, pi = acos(-1);
const long long LLINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 10;
int n;
LL a[N], len[N], val[N];
vector<int> g[N], G[N];
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N], din[N];
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
stk[++top] = u, in_stk[u] = true;
for (auto &v: g[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++scc_cnt;
int y;
do {
y = stk[top--];
in_stk[y] = false;
id[y] = scc_cnt;
Size[scc_cnt]++;
val[scc_cnt] += a[y];
len[scc_cnt]++;
} while (y != u);
}
}
void Count_D() {
rep (u, 1, n) {
for (auto &v: g[u]) {
if (id[u] != id[v]) {
dout[id[u]]++, din[id[v]]++;
G[id[u]].push_back(id[v]);
}
}
}
}
void init() {
timestamp = top = scc_cnt = 0;
rep (i, 1, n) {
g[i].clear();
G[i].clear();
dfn[i] = in_stk[i] = id[i] = Size[i] = din[i] = dout[i] = len[i] = val[i] = 0;
}
}
void topo() {
queue<int> q;
vector<LL> f(scc_cnt + 1), g(scc_cnt + 1);
rep (i, 1, scc_cnt) {
if (din[i] == 0) {
f[i] = len[i];
g[i] = val[i];
q.push(i);
}
}
while (q.size()) {
int u = q.front();
q.pop();
for (auto &v: G[u]) {
din[v]--;
if (f[v] < f[u] + len[v]) {
f[v] = f[u] + len[v];
g[v] = g[u] + val[v];
}
else if (f[v] == f[u] + len[v]) {
g[v] = min(g[v], g[u] + val[v]);
}
if (din[v] == 0) {
q.push(v);
}
}
}
LL res_len = 0, res_val = 0;
rep (i, 1, scc_cnt) {
if (res_len < f[i]) {
res_len = f[i];
res_val = g[i];
}
else if (res_len == f[i]) res_val = min(res_val, g[i]);
}
cout << res_len << " " << res_val << "\n";
}
void work() {
int m;
cin >> n >> m;
init();
rep (i, 1, n) cin >> a[i];
rep (i, 1, m) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
}
rep (i, 1, n) if (!id[i]) tarjan(i);
Count_D();
topo();
}
/*
*/