落谷 P4213 【模板】杜教筛（Sum）

题目链接 ：https://www.luogu.org/problem/P4213题目描述

分析：

改了好久，终于不TLE了
注意点：long long 尽量少用。对sum{mob}都用int；在get_ps中的(1+n)*n/2会爆int ； N的取值也得注意

• 前置知识：积性函数；狄利克雷卷积 h ( i ) = ∑ d ∣ i f ( d ) g ( i d ) 简 写 为 h = f ∗ g h(i)=\sum_{d|i}{f(d)g(\frac{i}{d})}简写为h=f*g h(i)=∑d∣i​f(d)g(di​)简写为h=f∗g
  对于μ，φ分别有（这两个东东好像都可以用狄利克雷卷积证，B站上电科大视频中有，不理解可以先记着）
  $$\begin{gathered} \mu \ast I=n\cdots ① \\ \phi \ast I=id \\ 注：函数I就是I(x)=1，函数id表示：id(x)=x \end{gathered}$$
  在推一遍杜教筛的套路式：
  求 s u m ( n ) : = ∑ i = 1 n f ( i ) 令 h = f ∗ g → h ( i ) = ∑ d ∣ i f ( i ) g ( i d ) ∑ i = 1 n h ( i ) = ∑ i = 1 n ∑ d ∣ i f ( i ) g ( i d ) 改 变 枚 举 顺 序 ： = ∑ d = 1 n f ( d ) ∑ i = 1 n / d g ( i ) = ∑ d = 1 n f ( i ) s u m ( n d ) 求sum(n):=\sum_{i=1}^n{f(i)}\\ 令h=f*g \ \ \ →h(i)=\sum_{d|i}{f(i)g(\frac{i}{d})}\\ \sum_{i=1}^nh(i)=\sum_{i=1}^n{\sum_{d|i}{f(i)g(\frac{i}{d})}}\\改变枚举顺序： \\=\sum_{d=1}^n{f(d)\sum_{i=1}^{n/d}{g(i)}}\\ =\sum_{d=1}^n{f(i)sum(\frac{n}{d})} 求sum(n):=i=1∑n​f(i)令h=f∗g   →h(i)=d∣i∑​f(i)g(di​)i=1∑n​h(i)=i=1∑n​d∣i∑​f(i)g(di​)改变枚举顺序：=d=1∑n​f(d)i=1∑n/d​g(i)=d=1∑n​f(i)sum(dn​)
  将d=1提出来
  ∑ i = 1 n h ( i ) = f ( 1 ) s u m ( n ) + ∑ d = 2 n f ( i ) s u m ( n d ) → f ( 1 ) s u m ( n ) = ∑ i = 1 n h ( i ) − ∑ d = 2 n f ( i ) s u m ( n d )              ⋯ ② \sum_{i=1}^n{h(i)}=f(1)sum(n)+\sum_{d=2}^n{f(i)sum(\frac{n}{d})} \\→f(1)sum(n)=\sum_{i=1}^n{h(i)}-\sum_{d=2}^n{f(i)sum(\frac{n}{d})}\;\;\;\;\;\;\cdots② i=1∑n​h(i)=f(1)sum(n)+d=2∑n​f(i)sum(dn​)→f(1)sum(n)=i=1∑n​h(i)−d=2∑n​f(i)sum(dn​)⋯②

对于求φ，有①式， ∑ i = 1 n φ \sum_{i=1}^n{φ} ∑i=1n​φ对应②式中的sum(n);$h=id=\phi \ast I$,f(1)=1；
对于μ，与φ类似

代码：

#include using namespace std;
#define N 5000010
#define ll long long unordered_map<int, ll > ps;
unordered_map<int, int > ms;int prime[N];
int phi[N];
int mob[N];
int mob_sum[N];
ll phi_sum[N];void get_eulur()
{memset(prime,0,sizeof(prime));phi[1]=1;mob[1]=1;phi_sum[1]=1;mob_sum[1]=1;for(int i=2;i<=N;i++){if(!prime[i]){prime[++prime[0]]=i;phi[i]=i-1;mob[i]=-1;}for(int j=1;j<=prime[0] && i*prime[j]<=N;j++){prime[i*prime[j]]=1;if(i%prime[j]==0){mob[i*prime[j]]=0;phi[i*prime[j]]=prime[j]*phi[i];break;}mob[i*prime[j]]=-mob[i];phi[i*prime[j]]=(prime[j]-1)*phi[i];}mob_sum[i]=mob_sum[i-1]+mob[i];phi_sum[i]=phi_sum[i-1]+phi[i];}
}inline ll get_ps(int n)
{if(n<=N) return phi_sum[n];if(ps.count(n)) return ps[n];ll ans=1LL*(1+n)*n/2;for(int l=2, r;l <= n;l=r+1){r=n/(n/l);ans -= (r-l+1)*get_ps(n/l);}return ps[n]=ans;
}inline int get_ms(int n)
{if(n<=N) return mob_sum[n];if(ms.count(n)) return ms[n];int ans=1;for(int l=2, r;l <= n;l=r+1){r=n/(n/l);ans -= (r-l+1)*get_ms(n/l);}return ms[n]=ans;
}int main()
{get_eulur();int T;int n;scanf("%d",&T);while(T--){scanf("%d",&n);printf("%lld %d\n",get_ps(n),get_ms(n));}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！