#G. 求约数个数之六

news/2024/11/13 6:36:21/

我们先求到区间[1..b]之间的所有约数之和

于是结果就等于

[1..b]之间的所有约数之和减去[1..a-1]之间的约数之和

很明显这两个问题是同性质的问题,只是右端点不同罢了.

明显对于1到N之间的数字,其约数范围也为1到N这个范围内。

于是我们可以枚举约数L,当然这个枚举不可能是for循环枚举,而是如上题一样“跳跃式的”

于是N/L就代表1到N之间有多少个数字是L的倍数,L也必为它们的约数。

例如当L=7时,N=20时

N/20=2,说明1到20以内有两个数字是7的倍数,易知为7,14,也就是说在算7和14的约数之和时,必然要将7统计进去。

然后这个算法高明的地方在于

当L=8,9,10时,N/L=2

于是这一段的L=7,R=10

于是这一段的约数之和为2*7+2*8+2*9+2*10=2*(7+8+9+10)=2*(7+10)*(10-7+1)/2

当统计完这一段后,设L=R+1=10+1=11

会发现11做为约数,只会出现1次

同时还会发现12,13,14.........20整个这一段的约数,都只会出现1次


#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll f(ll x)
{ll l = 1,r = 0,k = 0,ans = 0,m = 0;while(l <= x){r = x / (x / l);k = x / l;ans += k * (l + r) * (r - l + 1) / 2;l = r + 1;}return ans;
}
signed main()
{cin>>n>>m;cout<<f(m) - f(n - 1);return 0;
}

http://www.ppmy.cn/news/27494.html

相关文章

RPC(3)--基于 Nacos 的服务发现与负载均衡版

nacos:提供了一组简单易用的特性集&#xff0c;帮助您快速实现动态服务发现、服务配置、服务元数据及流量管理。Nacos 是构建以“服务”为中心的现代应用架构 (例如微服务范式、云原生范式) 的服务基础设施。 nacos架构如下(图片来源) 依赖包&#xff1a; <dependency>…

力扣-文章浏览

大家好&#xff0c;我是空空star&#xff0c;本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目&#xff1a;1148. 文章浏览二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.其他总结前言 一、题目&#xff1a;1148…

扬帆优配|反弹涨超70%,昨收三连板,稀土行业或迎大事件

本年第一批稀土挖掘锻炼目标行将发放。 2月22日晚&#xff0c;东易日盛公告称&#xff0c;公司收到董事、副总经理兼财务总监李双侠出具的《关于未严格执行股份减持方案的致歉函》&#xff0c;其此次减持方案已施行结束&#xff0c;但在施行减持方案时&#xff0c;因操作失误&a…

【性能测试】loadrunner(一)知识准备

【性能测试】loadrunner&#xff08;一&#xff09;知识准备 目录&#xff1a;导读 1.0. 前言 1.1 性能测试术语介绍 1.2 性能测试分类 1.3 HTTP我们需要知道的 1.4 Loadrunner 12.55安装 1.0. 前言 ​ 在性能测试中&#xff0c;牵扯到了许多比较杂的知识点&#xff0c;…

【python】考前复习,python基础语法知识点整理

文章目录1.常量与表达式2.变量和数据类型创建变量数据类型动态类型数据类型的转换3.注释4.字符串字符串的定义方式字符串的拼接字符串的格式化①字符串格式化的精度控制字符串的格式化②对表达式进行格式化5.从控制台输入(input)6.运算符算术运算符赋值运算符布尔类型和比较运算…

深入浅出 MySQL 索引(一)

MySQL 索引&#xff08;基础篇&#xff09; 你好&#xff0c;我是悟空。 本文目录如下&#xff1a; 一、前言 最近在梳理 MySQL 核心知识&#xff0c;刚好梳理到了 MySQL 索引相关的知识&#xff0c;我的文章风格很多都是原理 实战的方式带你去了解知识点&#xff0c;所以…

Nordic nRF芯片FDS模块学习

FDS系统学习 文章目录FDS系统学习一、ROM&#xff0c;RAM&#xff0c;FLASH作用二、ROM,RAM和FLASH在单片中的运作原理三、Flash访问模块FDS用法1. FDS在sdk_config.h中的配置2. fds_register()注册3. fds_record_write()写记录4. fds_record_find()查找5. fds_record_open()读…

秒杀服务------技术点及亮点

大技术使用Redisson使用Redisson在秒杀服务中有两个作用&#xff0c;一个是作为分布式锁来确保多个秒杀服务同时在线时同时上架秒杀商品&#xff0c;只允许有一个秒杀服务成功上架秒杀商品&#xff0c;其他的上架失败。第二个作用是作为分布式信号量&#xff0c;每个秒杀商品在…