思路:
yhx找的反演题
题解已经烂大街了
#pragma GCC optimize("O3") //By SiriusRen #include <bits/stdc++.h> using namespace std; typedef long long ll; int mu[1000500],prime[999999],vis[1000500],tot; void init(){ mu[1]=1; for(int i=2;i<=1000000;i++){ if(!vis[i])prime[++tot]=i,mu[i]=-1; for(int j=1;j<=tot&&i*prime[j]<=1000000;j++){ vis[i*prime[j]]=1;mu[i*prime[j]]=-mu[i]; if(i%prime[j]==0){mu[i*prime[j]]=0;break;} } } } ll f(ll n){ ll res=0; for(ll i=1;i*i*i<=n;res-=5,i++) for(ll j=i;i*j*j<=n;j++) res+=(n/i/j-j+1)*6-(i==j?(n/i/j-j)*3:3); return res; } ll solve(ll n){ ll res=0; for(ll i=1;i*i<=n;i++)res+=mu[i]?mu[i]*f(n/i/i):0; return (res+n)/2; } int main(){ init();ll a,b; scanf("%lld%lld",&a,&b); printf("%lld\n",solve(b)-solve(a-1)); }