扬中会建网站,优化公司股权结构,远程服务器安装wordpress,有哪些网站建设公司题目
传送门
思路
考场上的思路和正解差远了#xff0c;属实是反演学魔怔了。
首先#xff0c;对于所有的 x x x#xff0c;它可以通过 2 x 2x 2x 和 2 2 2 连通#xff0c;而 2 2 2 又可以和所有 m i n p ≤ ⌊ n 2 ⌋ minp\leq \left\lfloor\frac{n}{2}\right\…题目
传送门
思路
考场上的思路和正解差远了属实是反演学魔怔了。
首先对于所有的 x x x它可以通过 2 x 2x 2x 和 2 2 2 连通而 2 2 2 又可以和所有 m i n p ≤ ⌊ n 2 ⌋ minp\leq \left\lfloor\frac{n}{2}\right\rfloor minp≤⌊2n⌋ 的数连通。所以只有 p ⌊ n 2 ⌋ p\left\lfloor\frac{n}{2}\right\rfloor p⌊2n⌋ 是被孤立的点。
那么答案就可以转换成 ∑ u 2 n − 1 ∑ v u 1 n [ m i n p ( u ) ⌊ n 2 ⌋ m i n p ( v ) ⌊ n 2 ⌋ ] u v ∑ u 2 n − 1 ∑ v u 1 n u v − ∑ p ⌊ n 2 ⌋ p ( ∑ v p v ∑ u p u ) ∑ p 1 ⌊ n 2 ⌋ p 1 ∑ p 2 p 1 p 2 ∑ u 2 n − 1 ∑ v u 1 n u v − ∑ p ⌊ n 2 ⌋ p ∑ v 2 n v 1 2 ( ( ∑ p ⌊ n 2 ⌋ p ) 2 ∑ p ⌊ n 2 ⌋ p 2 ) \sum_{u2}^{n-1}\sum_{vu1}^n[minp(u)\left\lfloor\frac{n}{2}\right\rfloor \ minp(v)\left\lfloor\frac{n}{2}\right\rfloor]uv\\ \sum_{u2}^{n-1}\sum_{vu1}^nuv-\sum_{p\left\lfloor\frac{n}{2}\right\rfloor}p\left(\sum_{vp}v\sum_{up}u \right)\sum_{p_1\left\lfloor\frac{n}{2}\right\rfloor}p_1\sum_{p_2p_1}p_2\\ \sum_{u2}^{n-1}\sum_{vu1}^nuv-\sum_{p\left\lfloor\frac{n}{2}\right\rfloor}p\sum_{v2}^nv\frac{1}{2}\left(\left(\sum_{p\left\lfloor\frac{n}{2}\right\rfloor}p\right)^2\sum_{p\left\lfloor\frac{n}{2}\right\rfloor}p^2\right) u2∑n−1vu1∑n[minp(u)⌊2n⌋minp(v)⌊2n⌋]uvu2∑n−1vu1∑nuv−p⌊2n⌋∑p(vp∑vup∑u)p1⌊2n⌋∑p1p2p1∑p2u2∑n−1vu1∑nuv−p⌊2n⌋∑pv2∑nv21 p⌊2n⌋∑p 2p⌊2n⌋∑p2
所以我们只需要用 min25筛 求出质数的和还有平方和就可以啦。用 g ( n , ∣ P ∣ ) g(n,|P|) g(n,∣P∣) 即可。 注意不要跑两遍会T。 ⌊ n 2 ⌋ \left\lfloor\frac{n}{2}\right\rfloor ⌊2n⌋ 是在整除分块中求过的可以直接用。
代码
#includebits/stdc.h
#define int long longusing namespace std;
const int N1e67,inf1e18,mod998244353;
int sqr,n,tot;
vectorint sp1(N),sp2(N),g1(N),g2(N),w(N),id1(N),id2(N),p;
int power(int x,int t)
{int b1;while(t){if(t1) bb*x%mod;xx*x%mod; t1;}return b;
}
void init(int n)
{p.push_back(0);tot0;vectorbool bz(n1);for(int i2; in; i){if(!bz[i]){p.push_back(i);int nowp.size()-1;sp1[now](sp1[now-1]i)%mod;sp2[now](sp2[now-1]i*i%mod)%mod;}for(auto j:p){if(!j) continue;if(i*jn) break;bz[i*j]1;if(i%j0) break;}}
}
void O_o()
{cinn;sqrsqrt(n);init(sqr);int inv2power(2,mod-2),inv3power(3,mod-2);for(int i1,j; in; ij1){jn/(n/i);w[tot]n/i;int noww[tot]%mod;g1[tot]now*(now1)/2%mod-1;g2[tot]now*(now1)%mod*(2*now1)%mod*inv2%mod*inv3%mod-1;if(w[tot]sqr) id1[w[tot]]tot;else id2[n/w[tot]]tot;}for(int i1; ip.size(); i){for(int j1; jtot,p[i]*p[i]w[j]; j){int kw[j]/p[i]sqr?id1[w[j]/p[i]]:id2[n/(w[j]/p[i])];//g(w[j],i) g(w[j],i-1) - f(p[i])*(g(w[k],j-1)-sp[i-1])(g1[j]-p[i]*(g1[k]-sp1[i-1])%mod)%mod;(g2[j]-p[i]*p[i]%mod*(g2[k]-sp2[i-1])%mod)%mod;}}int f1g1[1],f2g2[1];//g(n,|P|)int kn/2sqr?id1[n/2]:id2[n/(n/2)];int h1g1[k],h2g2[k];//g(n/2,|P|)n%mod;int ansinv2*(inv2*(n*n%modn)%mod*(n*(n-1)%mod-2)%mod-inv2*inv2%mod*n%mod*n%mod*(n-1)%mod*(n-1)%mod2-inv2*inv3%mod*n%mod*(n-1)%mod*(2*n-1)%mod)%mod;ansans-(n*(n1)/2%mod-1)*(f1-h1)%mod((f1-h1)*(f1-h1)%mod-(f2-h2))*inv2%mod(f2-h2);ans%mod;(ansmod)%mod;coutans\n;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);coutfixedsetprecision(2);int T1;
// cinT;while(T--){O_o();}
}
