洛谷 P10584 [蓝桥杯 2024 国 A] 数学题(整除分块+杜教筛)

题目

思路来源

登录 - Luogu Spilopelia

题解

参考了两篇洛谷题解,第一篇能得出这个式子,第二篇有比较严格的复杂度分析

结合去年蓝桥杯洛谷P9238,基本就能得出这题的正确做法

代码

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<map>
#include<unordered_map>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e7+10;
bool ok[N];
int pr[N/10],mu[N],ans[N],cnt,up;
unordered_map<int,int>smu;
unordered_map<ll,ll>smu2;
ll n,m;
void sieve(ll n){mu[1]=1;ans[1]=1;for(ll i=2;i<N;++i){if(!ok[i]){pr[cnt++]=i;mu[i]=-1;}for(int j=0;j<cnt;++j){ll k=i*pr[j];if(k>=N)break;ok[k]=1;if(i%pr[j]==0){mu[k]=0;break; }mu[k]=-mu[i];}ans[i]+=ans[i-1]+(mu[i]!=0);mu[i]+=mu[i-1];}
}
int djsmu(int n){if(n<N)return mu[n];if(smu.count(n))return smu[n];int ans=1;for(int l=2,r;l<=n;l=r+1){r=n/(n/l);ans=ans-(r-l+1)*djsmu(n/l);}return smu[n]=ans;
}
ll cal(ll n){if(n<N)return ans[n];if(smu2.count(n))return smu2[n];ll res=0;for(ll l=1,r,v;l*l<=n;l=r+1){v=n/l/l;r=sqrt(n/v);res+=v*(djsmu(r)-djsmu(l-1));}return smu2[n]=res;
}
int main(){cin>>n>>m;sieve(n);ull ans=0;for(ll l=1,r,x,y;l<=min(n,m);l=r+1){x=sqrt(n/l),y=sqrt(m/l);r=min(n/(x*x),m/(y*y));ans+=1ull*(cal(r)-cal(l-1))*x*y;}cout<<ans<<endl;return 0;
} 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/359879.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

NC--介绍-未加密加密后-流量抓包对比

免责声明:本节仅做技术交流与学习... 目录 介绍: 用法: 未加密--流量抓包 加密: 攻击端 靶机 抓包分析: 介绍: nc 是一个Linux环境下常用的工具命令&#xff0c;可以用来帮助开发者查询和解决网路问题&#xff0c;通常被认为是 NetCat 工具的缩写&#xff0c;在网络工具…

Java——泛型

前言&#xff1a; 泛型类&#xff0c;泛型方法&#xff0c;泛型接口&#xff0c;通配符&#xff0c;类型擦除 文章目录 一、 泛型1.1、泛型的基本概念1.2 泛型的使用 三、通配符&#xff08;Wildcard&#xff09;四、类型擦除&#xff08;Type Erasure&#xff09;五、泛型的局…

React Native性能优化红宝书

一、React Native介绍 React Native 是Facebook在React.js Conf2015 推出的开源框架&#xff0c;使用React和应用平台的原生功能来构建 Android 和 iOS 应用。通过 React Native&#xff0c;可以使用 JavaScript 来访问移动平台的 API&#xff0c;使用 React 组件来描述 UI 的…

ONLYOFFICE 文档 8.1 现已发布:功能全面的 PDF 编辑器、幻灯片版式等等

0、前言 在技术的快速发展和工作方式的持续演进下&#xff0c;现代办公软件正变得越来越强大和多样化。ONLYOFFICE&#xff0c;作为市场上备受瞩目的一体化办公解决方案&#xff0c;以其全面的文档编辑、表格处理和演示制作功能&#xff0c;满足了用户在不同办公场景下的需求。…

安卓设备优雅的命令 adb 以及 优秀的控制 scrcpy

一、背景 如果有多台安卓设备&#xff0c;并为这些设备安装软件&#xff0c;一个个使用u盘再加上鼠标操作虽然可以做到&#xff0c;但是大概率比较麻烦。试想下&#xff0c;如果坐在电脑旁边&#xff0c;就能鼠标在电脑上点点就能解决问题&#xff0c;是多么优雅的一件事情。 …

使用上海云盾 CDN 和 CloudFlare 后 Nginx、 WordPress、 Typecho 获取访客真实 IP 方法

最近因为被 DDoS/CC 攻击的厉害,明月就临时的迁移了服务器,原来的服务器就空置下来了,让明月有时间对服务器进行了重置重新部署安装生产环境。因为站点同时使用了上海云盾和 CloudFlare(具体思路可以参考【国内网站使用国外 CloudFlare CDN 的思路分享】一文)两个 CDN 服务…

Docker--基础详解

目录 Docker介绍 Docker与传统虚拟机相比的优势 Docker基础插件 Docker镜像 容器和仓库 Docker介绍 Docker 是一个开源的应用容器引擎&#xff0c;基于 Go 语言开发&#xff0c;遵从Apache2.0开源协议&#xff0c;依赖Linux内核的Cgroup和Namespace等技术&#xff0c;对进…

快速欧氏聚类与普通欧氏聚类比较

1、前言 文献《FEC: Fast Euclidean Clustering for Point Cloud Segmentation》介绍了一种快速欧氏聚类方法,大概原理可以参考如下图,具体原理可以参考参考文献。 2、时间效率比较:快速欧氏聚类VS普通欧氏聚类 网上搜集的快速欧式聚类,与自己手写的普通欧式聚类进行对比,…

“了解MySQL中的enum枚举数据类型“

目录 # 开篇 1. 创建包含枚举类型的表 2. 插入枚举类型的数据 3. 查询包含枚举类型的表 4. 更新枚举类型的数据 5. 使用枚举类型的好处 注意事项 示例总结 附加 # 开篇 在数据库中&#xff0c;枚举&#xff08;ENUM&#xff09;是一种数据类型&#xff0c;用于存储一组…

uniapp中Error: project.configjson: libVersion 字段需为 string. string

错误如下 找到manifestjson文件到源码视图 添加这段代码"libVersion": "latest",即可

【WEB前端2024】3D智体编程:乔布斯3D纪念馆-第46课-使用json文件

【WEB前端2024】3D智体编程&#xff1a;乔布斯3D纪念馆-第45课-使用头像 使用dtns.network德塔世界&#xff08;开源的智体世界引擎&#xff09;&#xff0c;策划和设计《乔布斯超大型的开源3D纪念馆》的系列教程。dtns.network是一款主要由JavaScript编写的智体世界引擎&…

在Maven工程中手动配置并测试SpringBoot(巨详)

本篇博客承继自博客&#xff1a; 在IDEA 2024.1.3 (Community Edition)中创建Maven项目_idea2024.1.3如何创建maven项目-CSDN博客 配置POM文件 打开工程中的pom.xml文件&#xff0c;先向其中写入 <parent><groupId>org.springframework.boot</groupId><…

【挑战100天首通《谷粒商城》】-【第一天】06、环境-使用vagrant快速创建linux虚拟机

文章目录 课程介绍1、安装 linux 虚拟机2、安装 VirtualBoxStage 1&#xff1a;开启CPU虚拟化Stage 2&#xff1a;下载 VirtualBoxStage 2&#xff1a;安装 VirtualBoxStage 4&#xff1a;安装 VagrantStage 4-1&#xff1a;Vagrant 下载Stage 4-2&#xff1a;Vagrant 安装Stag…

[职场] 线上面试的准备工作 #知识分享#经验分享#媒体

线上面试的准备工作 面对求职中的面试&#xff0c;应届毕业生该做些什么准备呢&#xff1f;在这里&#xff0c;向各位分享面试前做好预案不慌张几点准备。现在许多面试是通过线上形式进行的。对于求职者来说&#xff0c;要做好两手准备。在这里&#xff0c;重点与大家分享线上面…

Qt画实时曲线图

Qt引入QcustomPlot 首先下载QcustomPlot源代码&#xff0c;https://github.com/qcustomplot/qcustomplot 下载zip文件 运行所下载的项目生成库文件libqcustomplotd2.a文件和qcustomplotd2.dll文件。 在项目中添加printsupport。 并将qcustomplot.h文件和qcustomplot.cpp文…

基于matlab的图像二值化

1 原理 图像二值化的原理是将彩色或灰度图像转换为只包含两种颜色&#xff08;通常是黑色和白色&#xff09;的二值图像的过程。其关键是通过设定一个阈值&#xff0c;将图像中的像素点的灰度值与阈值进行比较&#xff0c;根据比较结果将像素点设置为白色或黑色。步骤如下&…

ElementPlus组件与图标按需自动引入

按需自动引入组件 1. 安装ElementPlus和自动导入ElementPlus组件的插件 pnpm install element-plus pnpm install -D unplugin-vue-components unplugin-auto-import 2. vite.config.ts进行修改 import { defineConfig } from vite import vue from vitejs/plugin-vue // …

2024CICE电博会·以“链主”企业为核心,推动产业链协同发展

随着全球科技日新月异的发展&#xff0c;消费电子产业已成为推动经济增长、改善人民生活的重要力量。中国国际消费电子博览会&#xff08;简称CICE电博会&#xff09;自2001年创办以来&#xff0c;已经走过了二十余个春秋&#xff0c;凭借其独特的地理位置优势、专业的组织策划…

如何开发、使用 Starter

开发 第一步&#xff1a;创建starter工程hello-spring-boot-starter并配置pom.xml文件 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchem…

趣味C语言——【猜数字】小游戏

&#x1f970;欢迎关注 轻松拿捏C语言系列&#xff0c;来和 小哇 一起进步&#xff01;✊ &#x1f389;创作不易&#xff0c;请多多支持&#x1f389; &#x1f308;感谢大家的阅读、点赞、收藏和关注&#x1f495; &#x1f339;如有问题&#xff0c;欢迎指正 感谢 目录 代码…