[BZOJ3944] Sum

題目描述：

solution

裸的杜教篩。

唯一的坑點在于卡常。

似乎ans1和ans2都杜教篩超時了。

然而用杜教篩求出ans2，并用求出ans1不超時？！？。

? ? ? #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=3e6+50; inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } map<int,int> Mu; int prime[MAXN],vis[MAXN],n,pnum=0,inv2,inv6,mu[MAXN]; inline void init() {mu[1]=1;for(int i=2;i<MAXN;i++) {if(!vis[i]) prime[++pnum]=i,mu[i]=-1;for(int t,j=1;j<=pnum&&i*prime[j]<MAXN;j++) {vis[t=i*prime[j]]=1;if (!(i%prime[j])) {mu[t]=0;break;}mu[t]=-mu[i];}}for(int i=1;i<MAXN;i++) mu[i]=mu[i-1]+mu[i]; } inline ll get_mu(ll n) {if (n<MAXN) return mu[n];if (Mu[n]) return Mu[n];ll T=2,res=1;while(T<=n){ll pre=T;T=n/(n/T);res=res-1ll*(T-pre+1)*get_mu(n/T);T++;}return Mu[n]=res; }inline ll get_phi(ll n) {ll ans=0;for (ll T=1,pre;T<=n;T=pre+1){pre=n/(n/T);ans+=1ll*(n/T)*(n/T+1)/2*(1ll*get_mu(pre)-1ll*get_mu(T-1));}return ans; }int main() {int t=read();init();while(t--) {int n=read();printf("%lld %lld\n",get_phi(n),get_mu(n));}return 0; }???

?

總結

以上是生活随笔為你收集整理的[BZOJ3944] Sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。