bzoj2301 problem b-白红宇的个人博客

bzoj2301 problem b

发布日期：2022-02-22 18:04:14 浏览次数：9 分类：技术文章

本文共 856 字，大约阅读时间需要 2 分钟。

题面

对于给出的 n 个询问，每次求有多少个数对 (x,y) ，满足 a ≤ x ≤ b ， c ≤ y ≤ d ，且gcd(x,y) = k ， gcd(x,y) 函数为 x 和 y 的最大公约数。

懵逼鸟斯繁衍裸题

线性筛出μ函数

再分块求出μ和这一段值的乘积

code：

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=1e7+5;int mu[maxn];int p[maxn];int pcnt;int phi[maxn];int vis[maxn];int sum[maxn];void prev(){	mu[1]=1;	for(int i=2;i<=1e7;++i){		if(!vis[i]){			p[++pcnt]=i;			mu[i]=-1;		}		for(int j=1;i*p[j]<=1e7&&j<=pcnt;++j){			mu[i*p[j]]=-mu[i];			vis[i*p[j]]=1;			if(i%p[j]==0){				mu[i*p[j]]=0;				break;			}		}	}	for(int i=1;i<=1e7;++i){		sum[i]=sum[i-1]+mu[i];	}}int calc(int n,int m){	if(n
         
          >T;	while(T--){		cin>>a>>b>>c>>d>>k;		a--;		c--;		a/=k;b/=k;c/=k;d/=k;		cout<<(calc(b,d)-calc(a,d)-calc(c,b)+calc(a,c))<

转载于:https://www.cnblogs.com/eric-walker/p/9406643.html

转载地址：https://blog.csdn.net/dengxingrao0615/article/details/102231347 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：搜索（靶形数独）

下一篇：链表实现队列（指针）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章