BZOJ 2440 2301 莫比乌斯应用

2024-08-31 12:48
文章标签 应用 bzoj 莫比 乌斯 2440 2301

本文主要是介绍BZOJ 2440 2301 莫比乌斯应用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://www.lydsy.com/JudgeOnline/problem.php?id=2440

Description

小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些
数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而
这丝毫不影响他对其他数的热爱。 
这天是小X的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一
个小X讨厌的数。他列出了所有小X不讨厌的数,然后选取了第 K个数送给了
小X。小X很开心地收下了。 
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗?

Input

包含多组测试数据。文件第一行有一个整数 T,表示测试
数据的组数。 
第2 至第T+1 行每行有一个整数Ki,描述一组数据,含义如题目中所描述。 

Output

含T 行,分别对每组数据作出回答。第 i 行输出相应的
第Ki 个不是完全平方数的正整数倍的数。

Sample Input

4
1
13
100
1234567

Sample Output

1
19
163
2030745

HINT

对于 100%的数据有 1 ≤ Ki ≤ 10^9

,    T ≤ 50


题目意思:求第k个不完整平方数。
无平方因子数(Square-Free Number),即分解之后所有质因数的次数都为1的数
首先二分答案 问题转化为求[1,x]之间有多少个无平方因子数
根据容斥原理可知 对于sqrt(x)以内所有的质数 有
  x以内的无平方因子数
=0个质数乘积的平方的倍数的数的数量(1的倍数)
-每个质数的平方的倍数的数的数量(9的倍数,25的倍数,...)

+每2个质数乘积的平方的倍数的数的数量(36的倍数,100的倍数,...)-...

容易发现每个乘积a^2前面的符号恰好是mu[a]

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define maxn 1000000
#define LL long long
LL mu[maxn+1];
LL pri[maxn+1],tot;
bool isprime[maxn+1];
void init(){tot=0;isprime[0]=isprime[1]=false;for(LL i=2;i<=maxn;i++)isprime[i]=true;for(LL i=2;i<=maxn;i++){if(isprime[i]){pri[tot++]=i;mu[i]=-1;}for(LL j=0;j<tot&&i*pri[j]<=maxn;j++){isprime[i*pri[j]]=0;if(i%pri[j]==0){mu[i*pri[j]]=0;break;}mu[i*pri[j]]=-mu[i];}}
}
LL calc(LL m){LL res=0;for(LL i=2;i*i<=m;i++){LL tmp=m/(i*i);res-=mu[i]*tmp;}return res;
}
LL bin(LL m){LL res=m;for(LL i=2;i*i<=m;i++){LL tmp=m/(i*i);res+=mu[i]*tmp;}return res;
}
int main(){init();LL T;scanf("%lld",&T);while(T--){LL k;scanf("%lld",&k);
//        LL t = k + calc(k);
//        while(t-calc(t)!=k){
//            t = k + calc(t);
//        }LL l=k + calc(k),r=k+k,tt,cnt;
//        cout<<calc(4)<<endl;while(l<=r){tt=(l+r)>>1;cnt=bin(tt);
//            cout<<cnt<<" "<<l<<" "<<r<<" "<<tt<<endl;if(cnt>k)r=tt-1;else if(cnt<k)l=tt+1;else if(cnt==k&&calc(tt-1)==calc(tt)){break;}else{r=tt-1;}}
//        cout<<cnt<<" "<<l<<" "<<r<<" "<<tt<<endl;printf("%lld\n",tt);}return 0;
}

Description

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



Input

第一行一个整数n,接下来n行每行五个整数,分别表示a、b、c、d、k

 

Output

共n行,每行一个整数表示满足要求的数对(x,y)的个数

 

Sample Input

2

2 5 1 5 1

1 5 1 5 2



Sample Output


14

3




题意很清楚了,求多少个(x,y)对。

那么令f(k)表示为gcd(x,y)=k的个数,其中a<=x<=b  && c<=y<=d

如此,对应F(k)表示gcd(x,y)=k倍数的数的个数。

对于这个题,假设用函数calc(b,d)计算表示为1<=x<=b  && 1<=y<=d的gcd(x,y)==k的对数,那么最终结果为:

calc(b,d)-calc(a-1,d)-calc(b,c-1)+cala(a-1,c-1)

如此一来,计算F(k)就方便了,比如calc(b,d)的话,

F[k]=(b/k)*(d/k)。

然后通过莫比乌斯反演得到f(k)即为结果。

但是会TLE。

需要优化,

观察式子,发现  (n/k)      最多有     2sqrt(n)  个取值
那么   (n/k)*(m/k)            就至多有       2(sqrt(n)+sqrt(m))            个取值
枚举这 些 取值,对莫比乌斯函数维护一个前缀和,就可以在  sqrt(n)        时间内出解
总时间复杂度nsqrt(n)
枚举除法的取值这种方法在莫比乌斯反演的应用当中非常常用,且代码并不难写

if(n>m) swap(n,m);
for(i=1;i<=n;i=last+1)
{
last=min(n/(n/i),m/(m/i));
re+=(n/i)*(m/i)*(sum[last]-sum[i-1]);
}
return re;

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 50000
int mu[maxn+1],sum[maxn+1];
int notprime[maxn+1];
int pri[maxn+1],tot;
void init(){mu[1]=1;sum[1]=1;for(int i=2;i<=maxn;i++){if(!notprime[i]){pri[tot++]=i;mu[i]=-1;}for(int j=0;j<tot&&pri[j]*i<=maxn;j++){notprime[i*pri[j]]=1;if(i%pri[j]==0){mu[i*pri[j]]=0;break;}mu[i*pri[j]]=-mu[i];}sum[i]=sum[i-1]+mu[i];}
}
/****************************************************
int calc(int n,int m,int k){    //TLE  case T moreif(n>m)swap(n,m);int res=0;for(int i=k;i<=n;i+=k)res+=mu[i/k]*(n/i)*(m/i);return res;
}
*****************************************************/
int calc(int n,int m,int k){    //TLE  case T moreif(n>m)swap(n,m);n/=k,m/=k;int res=0,last;for(int i=1;i<=n;i=last+1){last=min(n/(n/i),m/(m/i));
//        cout<<i<<" "<<k<<endl;res+=(sum[last]-sum[i-1])*(n/i)*(m/i);}return res;
}
int main(){init();int T;scanf("%d",&T);while(T--){int a,b,c,d,k;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);int ans=calc(b,d,k)-calc(a-1,d,k)-calc(b,c-1,k)+calc(a-1,c-1,k);printf("%d\n",ans);}return 0;
}



这篇关于BZOJ 2440 2301 莫比乌斯应用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1123946

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

zoj3820(树的直径的应用)

题意:在一颗树上找两个点,使得所有点到选择与其更近的一个点的距离的最大值最小。 思路:如果是选择一个点的话,那么点就是直径的中点。现在考虑两个点的情况,先求树的直径,再把直径最中间的边去掉,再求剩下的两个子树中直径的中点。 代码如下: #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#

【区块链 + 人才服务】可信教育区块链治理系统 | FISCO BCOS应用案例

伴随着区块链技术的不断完善,其在教育信息化中的应用也在持续发展。利用区块链数据共识、不可篡改的特性, 将与教育相关的数据要素在区块链上进行存证确权,在确保数据可信的前提下,促进教育的公平、透明、开放,为教育教学质量提升赋能,实现教育数据的安全共享、高等教育体系的智慧治理。 可信教育区块链治理系统的顶层治理架构由教育部、高校、企业、学生等多方角色共同参与建设、维护,支撑教育资源共享、教学质量评估、

AI行业应用(不定期更新)

ChatPDF 可以让你上传一个 PDF 文件,然后针对这个 PDF 进行小结和提问。你可以把各种各样你要研究的分析报告交给它,快速获取到想要知道的信息。https://www.chatpdf.com/

【区块链 + 人才服务】区块链集成开发平台 | FISCO BCOS应用案例

随着区块链技术的快速发展,越来越多的企业开始将其应用于实际业务中。然而,区块链技术的专业性使得其集成开发成为一项挑战。针对此,广东中创智慧科技有限公司基于国产开源联盟链 FISCO BCOS 推出了区块链集成开发平台。该平台基于区块链技术,提供一套全面的区块链开发工具和开发环境,支持开发者快速开发和部署区块链应用。此外,该平台还可以提供一套全面的区块链开发教程和文档,帮助开发者快速上手区块链开发。

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

基于 YOLOv5 的积水检测系统:打造高效智能的智慧城市应用

在城市发展中,积水问题日益严重,特别是在大雨过后,积水往往会影响交通甚至威胁人们的安全。通过现代计算机视觉技术,我们能够智能化地检测和识别积水区域,减少潜在危险。本文将介绍如何使用 YOLOv5 和 PyQt5 搭建一个积水检测系统,结合深度学习和直观的图形界面,为用户提供高效的解决方案。 源码地址: PyQt5+YoloV5 实现积水检测系统 预览: 项目背景