[反演] LOJ #509. 「LibreOJ NOI Round #1」动态几何问题

μ2(n)=∑d2|nμ(d)

然后就是xjb推

反正退役了 我也就弃坑了 95分代码

复杂度分析及优化详见 官方题解

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;

ll n,m;

const int maxn=;
const int N=maxn+;

int prime[],num;
int mu[N],mu2[N]; 

const int P=;

inline void Pre(int n){
  mu[]=; int *vst=mu2;
  for (int i=;i<=n;i++){
    if (!vst[i]) prime[++num]=i,mu[i]=-; ll t;
    for (int j=;j<=num && (t=(ll)i*prime[j])<=n;j++){
      vst[t]=;
      if (i%prime[j]==){
    mu[t]=; break;
      }else
    mu[t]=-mu[i];
    }
  }
  for (int i=;i<=n;i++) mu2[i]=((bool)mu[i])+mu2[i-],mu[i]=mu[i-]+mu[i];
}

inline ll S(ll n){
  if (n<=maxn) return mu2[n];
  int x=sqrt(n); ll ret=;
  for (int i=,j;i<=x;i=j+){
    ll t=n/i/i; j=sqrt(n/t);
    ret+=(mu[j]-mu[i-])*t;
  }
  return ret;
}

int main(){
  Pre(maxn);
  scanf("%lld%lld",&n,&m);
  if (n>m) swap(n,m); ll ans=;
  ll last=,cur;
  for (ll i=,j;i<=n;i=j+){
    ll t1=sqrt(n/i),t2=sqrt(m/i);
    j=min(n/(t1*t1),m/(t2*t2));
    cur=S(j);
    ans+=(cur-last)*t1*t2;
    last=cur;
  }
  printf("%lld\n",ans);
  return ;
}