牛客挑战赛46 E（数论）

[题目链接](https://ac.nowcoder.com/acm/contest/9510/E) ------------ 设$s(n)=\sum_{i=1}^n\left \lfloor \frac{n}{i} \right \rfloor$，$f(n)=\sum_{p|n}s(p)$ 注意到$\sigma _0(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$ 原式 $=\sum_{i=1}^n \sum_{j|m!} \sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$ $=\sum_{x=1}^n \left \lfloor \frac{n}{x} \right \rfloor \sum_{y|m!} s(\left \lfloor \frac{m!}{y} \right \rfloor) [gcd(x,y)=1]$ $=\sum_{x=1}^n \left \lfloor \frac{n}{x} \right \rfloor \sum_{y|m!} s(\left \lfloor \frac{m!}{y} \right \rfloor) \sum_{p|x,p|y} \mu(p)$ $=\sum_{p|m!} \mu(p) s(\left \lfloor \frac{n}{p} \right \rfloor) f(\left \lfloor \frac{m!}{p} \right \rfloor)$ $f(\left \lfloor \frac{m!}{p} \right \rfloor)$本质相当于$p$的所有倍数的因子个数之和 由于莫比乌斯函数的性质，$p$的所有质因子最高次幂为$1$ 考虑枚举$m!$中的质因子$d$，再枚举$p$中是否有因子$d$计算 复杂度$O(2^t),t=\frac{m}{logm} $ ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod=998244353; ll n,m,ans; vector< pair<int,int> > p; ll s(ll n) { ll res=0; for(ll l=1,r=0;l<=n;l=r+1) { r=n/(n/l); res=(res+(r-l+1)*(n/l)%mod)%mod; } return res; } void dfs(int k,ll d,ll mu,ll f) { if(k==p.size()) { ans=(ans+mu*s(n/d)*f%mod+mod)%mod; return ; } dfs(k+1,d,mu,(p[k].second+2)*(p[k].second+1)/2*f%mod); dfs(k+1,d*p[k].first,-mu,(p[k].second+1)*p[k].second/2*f%mod); } int main() { scanf("%lld%lld",&n,&m); auto v=[&](int x) { for(int i=2;i<x;i++) if(x%i==0)return 0; return 1; }; for(int i=2;i<=m;i++)if(v(i)) { int c=0,tmp=m; while(tmp)c+=tmp/i,tmp/=i; p.push_back(make_pair(i,c)); } dfs(0,1,1,1); printf("%lld\n",ans); return 0; } ```