BZOJ3944 Sum 数论 杜教筛

 ​

题目传送门 - BZOJ3944题意

　　多组数据（组数<=10)。

　　每组数据一个正整数$n(n\leq 10^{10})$。

　　让你求$\sum_{i=1}^{n}\varphi(i)$以及$\sum_{i=1}^{n}\mu(i)$。

题解

　　杜教筛模版题。

　　杜教筛学习->传送门

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e6+5;
int lim=2e6,T;
LL n,prime[N],pcnt,u[N],phi[N],U[N],Phi[N];
int vis[N],mark=0;
void init(int n){
  memset(phi,0,sizeof phi);
  u[1]=phi[1]=1;
  for (int i=2;i<=n;i++){
    if (!phi[i])
      prime[++pcnt]=i,u[i]=-1,phi[i]=i-1;
    for (int j=1;j<=pcnt&&prime[j]*i<=n;j++){
      int k=prime[j]*i;
      if (i%prime[j])
        u[k]=-u[i],phi[k]=phi[i]*(prime[j]-1);
      else {
        u[k]=0,phi[k]=phi[i]*prime[j];
        break;
      }
    }
  }
  for (int i=2;i<=n;i++)
    u[i]+=u[i-1],phi[i]+=phi[i-1];
  memset(vis,0,sizeof vis);
}
void solve(LL x){
  if (x<=lim)
    return;
  LL y=n/x;
  if (vis[y]==mark)
    return;
  vis[y]=mark;
  U[y]=1,Phi[y]=x*(x+1)/2;
  for (LL i=2,j;i<=x;i=j+1){
    j=x/(x/i);
    solve(x/i);
    U  [y]-=(x/i<=lim?u  [x/i]:U  [n/(x/i)])*(j-i+1);
    Phi[y]-=(x/i<=lim?phi[x/i]:Phi[n/(x/i)])*(j-i+1);
  }
}
int main(){
  init(lim);
  scanf("%d",&T);
  while (T--){
    scanf("%lld",&n);
    if (n<=lim)
      printf("%lld %lld\n",phi[n],u[n]);
    else {
      mark++;
      solve(n);
      printf("%lld %lld\n",Phi[1],U[1]);
    }
  }
  return 0;
}