Bzoj 2301
coc youyl
posted @ 2015年6月27日 18:54
in bzoj
, 700 阅读
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2301
题目分类：数论，莫比乌斯反演
题意：
n个询问，每次询问有多少个数对(x,y)满足a<=x<=b且c<=y<=d且gcd(x,y)=k
题解：
使用容斥原理可以将问题转化成bzoj 1101这道题【f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)】
然后可以将问题转化成互质的数
可以通过一系列变换将式子转化为可以分块的式子
具体详见http://hzwer.com/4205.html
程序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include<cstdio>#include<algorithm>#include<cmath>using namespace std;long long n,x1,x2,x3,x4,m;long long miu[70000],isp[70000],cnt,pri[70000],summ[70000];inline void shai(){ miu[1]=1; for (long long i=2;i<=60000;i++) { if(isp[i]==0){cnt++;pri[cnt]=i;miu[i]=-1;} for (long long j=1;j<=cnt&&i*pri[j]<=60000;j++) { isp[i*pri[j]]=1; if(i%pri[j]==0){miu[i*pri[j]]=0;break;} else miu[i*pri[j]]=-miu[i]; } } for (long long i=1;i<=60000;i++) { summ[i]=summ[i-1]+miu[i]; }}inline long long query(long long x,long long y){ if(x>y)swap(x,y); long long pos=0,i=1,ans=0; while (i<=x) { pos=min(x/(x/i),y/(y/i)); ans+=(summ[pos]-summ[i-1])*(x/i)*(y/i); i=pos+1; }//printf("%lld %lld %lld\n",x,y,ans); return ans;}int main(){ shai(); scanf("%lld",&n); while (n--) { scanf("%lld %lld %lld %lld %lld",&x1,&x2,&x3,&x4,&m); x1--;x3--; printf("%lld\n",query(x2/m,x4/m)+query(x1/m,x3/m)-query(x1/m,x4/m)-query(x2/m,x3/m)); } return 0;} |
评论 (0)
