网站建设 响应式 北京,做网站 卖产品,申请免费建站,网页制作策划路程怎么写Problem - D - Codeforces
思路 只选两个小数计算贡献#xff0c;可对序列排序#xff0c;每对 ( i , j ) (i, j) (i,j) 其中 ( i j ) (ij) (ij)的的贡献是 g c d ( i , j ) ⋅ ( n − j ) gcd(i, j) \cdot (n - j) gcd(i,j)⋅(n−j) 通过预处理因数欧拉反演可…Problem - D - Codeforces
思路 只选两个小数计算贡献可对序列排序每对 ( i , j ) (i, j) (i,j) 其中 ( i j ) (ij) (ij)的的贡献是 g c d ( i , j ) ⋅ ( n − j ) gcd(i, j) \cdot (n - j) gcd(i,j)⋅(n−j) 通过预处理因数欧拉反演可将复杂度降为 O ( n V ) O(nV) O(nV) n Σ d ∣ n φ ( d ) 令 n g c d ( i , j ) 得到 g c d ( i , j ) Σ d ∣ ( i , j ) φ ( d ) Σ d ∣ i Σ d ∣ j φ ( d ) . 可以求 Σ i 1 n g c d ( i , n ) Σ i 1 n Σ d ∣ i Σ d ∣ n φ ( d ) Σ d ∣ n Σ i 1 n Σ d ∣ i φ ( d ) Σ d ∣ n n d φ ( d ) . 题目要求 Σ i 1 Σ j i 1 g c d ( a [ i ] , a [ j ] ) ⋅ ( n − j ) Σ j 1 n Σ i 1 j g c d ( a [ i ] , a [ j ] ) ⋅ ( n − j ) Σ j 1 n Σ d ∣ a [ j ] a [ j ] d φ ( d ) ⋅ ( n − j ) Σ j 1 n Σ d ∣ a [ j ] c n t [ d ] φ ( d ) ⋅ ( n − j ) . \begin{aligned} n \Sigma_{d | n} \varphi(d)\\ 令n gcd(i, \ j) \\ 得到gcd(i, \ j) \Sigma_{d | (i, \ j)} \varphi(d) \\ \Sigma_{d | i} \Sigma_{d | j} \varphi(d). \\\\ 可以求 \Sigma_{i 1} ^ n gcd(i, \ n) \Sigma_{i 1} ^ n \Sigma_{d | i} \Sigma_{d | n} \varphi(d) \\ \Sigma_{d | n} \Sigma_{i 1} ^ n \Sigma_{d | i} \varphi(d) \\ \Sigma_{d | n} \frac{n}{d} \varphi(d).\\\\ 题目要求 \Sigma_{i 1} \Sigma_{j i 1}gcd(a[i],\ a[j]) \cdot (n - j) \\ \Sigma_{j 1} ^ n \Sigma_{i 1} ^ jgcd(a[i], \ a[j]) \cdot(n - j) \\ \Sigma_{j 1} ^ n \Sigma_{d | a[j]} \frac{a[j]}{d} \varphi(d) \cdot(n - j) \\ \Sigma_{j 1} ^ n \Sigma_{d | a[j]} cnt[d] \varphi(d) \cdot(n - j). \end{aligned} n令n得到gcd(i, j)可以求Σi1ngcd(i, n)题目要求Σd∣nφ(d)gcd(i, j)Σd∣(i, j)φ(d)Σd∣iΣd∣jφ(d).Σi1nΣd∣iΣd∣nφ(d)Σd∣nΣi1nΣd∣iφ(d)Σd∣ndnφ(d).Σi1Σji1gcd(a[i], a[j])⋅(n−j)Σj1nΣi1jgcd(a[i], a[j])⋅(n−j)Σj1nΣd∣a[j]da[j]φ(d)⋅(n−j)Σj1nΣd∣a[j]cnt[d]φ(d)⋅(n−j). 参考博客欧拉函数|(扩展)欧拉定理|欧拉反演 - Morning_Glory - 博客园 (cnblogs.com)
另 一个序列的两两 g c d gcd gcd和 φ ( d ) ⋅ C ( c n t [ d ] , 2 ) \varphi(d) \cdot C(cnt[d], 2) φ(d)⋅C(cnt[d],2)仿照莫队可以推得当 c n t [ d ] cnt[d] cnt[d]增加1时对当前位置答案的影响为 φ ( d ) ⋅ c n t [ d ] \varphi(d) \cdot cnt[d] φ(d)⋅cnt[d]对每一位计算贡献后乘位权即可。 AC代码
#include bits/stdc.h
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
//#define int ll
#define pb push_back
#define eb emplace_back
#define m_p make_pair
const int mod 998244353;
#define mem(a,b) memset(a,b,sizeof a)
#define pii pairint,int
#define fi first
#define se second
const int inf 0x3f3f3f3f;
const int N 3e5 50;
//__builtin_ctzll(x);后导0的个数
//__builtin_popcount计算二进制中1的个数
int a[N];
vectorint fac[N];
bool is[N]; //筛数组
int pri[N]; //素数数组
int phi[N]; //欧拉函数
int tot0; //素数个数
int n;
ll cnt[N];void init(){for(int i1;iN;i){is[i]1;}is[0]is[1]0;phi[1]1;for(int i2;iN;i){if(is[i]){pri[tot]i;phi[i]i-1;}for(int j1;jtot pri[j]*iN;j){is[pri[j]*i]0;if(i%pri[j]0){phi[i*pri[j]]phi[i]*pri[j];break;}else{phi[i*pri[j]]phi[i]*(pri[j]-1);}}}
}void work() {int n;cin n;for (int i 1; i N; i) {cnt[i] 0;}int maxx 0;for (int i 1; i n; i) {cin a[i];}sort(a 1, a 1 n);ll ans 0;for (int i 1; i n; i) {ll now 0;for (auto x:fac[a[i]]) {now phi[x] * cnt[x];cnt[x];}ans now * (n - i);}cout ans \n;
}signed main() {io;int t 1;cin t;for (int i 1; i N; i) {for (int j 1; j * i N; j) {fac[i * j].pb(i);}}init();while (t--) {work();}return 0;
}Problem - E - Codeforces
思路 可以发现通过传递拓展到的边一定是将原有路径变短不符合我们需要的答案所以拓展是无用的操作只管原图即可。图中最难处理的是有向环有向环可以跑到环上任意一点出去自然联想 t a r j a n tarjan tarjan缩点缩点后在 D A G DAG DAG图上跑 d p dp dp就可以得到答案。 AC代码
#include bits/stdc.h
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
//#define int ll
#define pb push_back
#define eb emplace_back
#define m_p make_pair
const int mod 998244353;
#define mem(a,b) memset(a,b,sizeof a)
#define pii pairint,ll
#define fi first
#define se second
const ll inf 0x3f3f3f3f3f3f3f3f;
const int N 3e5 50;
//__builtin_ctzll(x);后导0的个数
//__builtin_popcount计算二进制中1的个数
int a[N];
int n, m, val[N], h[N], e[N], ne[N], idx;
int in[N];
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc; // 结点 i 所在 SCC 的编号
int sz[N]; // 强连通 i 的大小
ll sum[N]; // 强连通 i 的权值
pii dp[N];void add(int u, int v) {e[idx] v, ne[idx] h[u], h[u] idx;
}void tarjan(int u) {low[u] dfn[u] dfncnt, s[tp] u, in_stack[u] 1;for (int i h[u]; i; i ne[i]) {int v e[i];if (!dfn[v]) {tarjan(v);low[u] min(low[u], low[v]);} else if (in_stack[v]) {low[u] min(low[u], dfn[v]);}}if (dfn[u] low[u]) {sc;while (s[tp] ! u) {scc[s[tp]] sc;sz[sc];sum[sc] val[s[tp]];in_stack[s[tp]] 0;--tp;}scc[s[tp]] sc;sz[sc];sum[sc] val[s[tp]];in_stack[s[tp]] 0;--tp;}
}vectorint ed[N];void work() {cin n m;dfncnt tp sc idx 0;for (int i 1; i n; i) {h[i] 0;sum[i] dfn[i] low[i] s[i] in_stack[i] sz[i] scc[i] 0;in[i] 0;ed[i].clear();}for (int i 1; i n; i) {cin val[i];dp[i].fi 0;dp[i].se inf;}for (int i 1; i m; i) {int u, v;cin u v;add(u, v);}for (int i 1; i n; i) {if (!dfn[i]) tarjan(i);}for (int i 1; i n; i) {int u scc[i];for (int j h[i]; j ; j ne[j]) {int v scc[e[j]];if (u v) continue;ed[v].pb(u);in[u];}}queueintq;for (int i 1; i sc; i) {if (in[i] 0) {q.push(i);if (dp[i].fi sz[i]) dp[i].se min(dp[i].se, sum[i]);else if (dp[i].fi sz[i]) dp[i] {sz[i], sum[i]};}}while (!q.empty()) {int now q.front();q.pop();for (auto x: ed[now]) {in[x]--;if (dp[x].fi sz[x] dp[now].fi) dp[x].se min(dp[x].se, sum[x] dp[now].se);else if (dp[x].fi sz[x] dp[now].fi) dp[x] {sz[x] dp[now].fi, sum[x] dp[now].se};if (in[x] 0) {q.push(x);}}}ll len 0, ans inf;for (int i 1; i sc; i) {if (dp[i].fi len) len dp[i].fi, ans dp[i].se;else if (dp[i].fi len) ans min(ans, dp[i].se);}cout len ans \n;
}signed main() {io;int t 1;cin t;while (t--) {work();}return 0;
}
