# 【BZOJ】2301 [HAOI2011]Problem b &amp;&amp; 【BZOJ】1101 [POI2007]Zap 莫比乌斯函数+数论分块

xiaoxiao2021-02-28  4

i=1aj=1b[(i,j)=k]=i=1Aj=1B[(i,j)=1]=i=1Aj=1Be((i,j)) 我们知道 e=μ1 ，于是式子可以变成 i=1Aj=1Bd|(i,j)μ(d)=d=1min(A,B)μ(d)AdBd 然后就是喜闻乐见的数论分块了。

#include <cstdio> #include <cctype> #include <algorithm> using namespace std; typedef long long ll; const int N=5e4+10; int t,a,b,c,d,k,miu[N],p[N],num; bool bo[N]; inline char nc(void){ static char ch[100010],*p1=ch,*p2=ch; return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++; } inline void read(int &a){ static char c=nc();int f=1; for (;!isdigit(c);c=nc()) if (c=='-') f=-1; for (a=0;isdigit(c);a=(a<<3)+(a<<1)+c-'0',c=nc()); return (void)(a*=f); } inline void prime(int n){ miu[1]=1; for (int i=2; i<=n; ++i){ if (!bo[i]) p[++num]=i,miu[i]=-1; for (int j=1; j<=num&&p[j]*i<=n; ++j){ bo[p[j]*i]=1; if (i%p[j]==0) {miu[p[j]*i]=0;break;} else miu[p[j]*i]=-miu[i]; } } for (int i=2; i<=n; ++i) miu[i]+=miu[i-1]; return; } inline ll calc(int a,int b){ ll ret=0;a/=k,b/=k; for (int l=1,r; l<=a&&l<=b; l=r+1) r=min(a/(a/l),b/(b/l)),ret+=1ll*(miu[r]-miu[l-1])*(a/l)*(b/l); return ret; } int main(void){ for (prime(5e4),read(t); t; --t){ read(a),read(b),read(c),read(d),read(k),--a,--c; printf("%lld\n",calc(b,d)-calc(a,d)-calc(b,c)+calc(a,c)); } return 0; }

#include <cstdio> #include <algorithm> using namespace std; const int N=5e4+10; int t,a,b,k,p[N],miu[N],num; bool bo[N]; inline void get(int n){ miu[1]=1; for (int i=2; i<=n; ++i){ if (!bo[i]) p[++num]=i,miu[i]=-1; for (int j=1; j<=num&&p[j]*i<=n; ++j){ bo[p[j]*i]=1,miu[p[j]*i]=-miu[i]; if (i%p[j]==0) {miu[p[j]*i]=0;break;} } } for (int i=2; i<=n; ++i) miu[i]+=miu[i-1]; return; } inline int calc(int a,int b){ int ret=0; for (int l=1,r; l<=a&&l<=b; l=r+1) r=min(a/(a/l),b/(b/l)),ret+=1ll*(miu[r]-miu[l-1])*(a/l)*(b/l); return ret; } int main(void){ for (get(5e4),scanf("%d",&t); t; --t){ scanf("%d%d%d",&a,&b,&k); printf("%d\n",calc(a/k,b/k)); } return 0; }