首页 技术 正文
技术 2022年11月23日
0 收藏 597 点赞 2,783 浏览 2117 个字

首先看这道题目,我预感商数肯定是有规律的排列的,于是我打表找一下规律

100 / 1 = 100
100 / 2 = 50 
100 / 3 = 33 
100 / 4 = 25 
100 / 5 = 20 
100 / 6 = 16 
100 / 7 = 14 
100 / 8 = 12 
100 / 9 = 11 
100 / 10 = 10 
100 / 11 = 9  
100 / 12 = 8  
100 / 13 = 7  
100 / 14 = 7  
100 / 15 = 6  
100 / 16 = 6  
100 / 17 = 5  
100 / 18 = 5  
100 / 19 = 5  
100 / 20 = 5  
100 / 21 = 4  
100 / 22 = 4  
100 / 23 = 4  
100 / 24 = 4  
100 / 25 = 4  
100 / 26 = 3  
100 / 27 = 3  
100 / 28 = 3  
100 / 29 = 3  
100 / 30 = 3  
100 / 31 = 3  
100 / 32 = 3  
100 / 33 = 3  
100 / 34 = 2  
100 / 35 = 2  
100 / 36 = 2  
100 / 37 = 2  
100 / 38 = 2  
100 / 39 = 2  
100 / 40 = 2  
100 / 41 = 2  
100 / 42 = 2  
100 / 43 = 2  
100 / 44 = 2  
100 / 45 = 2  
100 / 46 = 2  
100 / 47 = 2  
100 / 48 = 2  
100 / 49 = 2  
100 / 50 = 2  
100 / 51 = 1  
100 / 52 = 1  
100 / 53 = 1  
100 / 54 = 1  
100 / 55 = 1  
100 / 56 = 1  
100 / 57 = 1  
100 / 58 = 1  
100 / 59 = 1  
100 / 60 = 1  
100 / 61 = 1  
100 / 62 = 1  
100 / 63 = 1  
100 / 64 = 1  
100 / 65 = 1  
100 / 66 = 1  
100 / 67 = 1  
100 / 68 = 1  
100 / 69 = 1  
100 / 70 = 1  
100 / 71 = 1  
100 / 72 = 1  
100 / 73 = 1  
100 / 74 = 1  
100 / 75 = 1  
100 / 76 = 1  
100 / 77 = 1  
100 / 78 = 1  
100 / 79 = 1  
100 / 80 = 1  
100 / 81 = 1  
100 / 82 = 1  
100 / 83 = 1  
100 / 84 = 1  
100 / 85 = 1  
100 / 86 = 1  
100 / 87 = 1  
100 / 88 = 1  
100 / 89 = 1  
100 / 90 = 1  
100 / 91 = 1  
100 / 92 = 1  
100 / 93 = 1  
100 / 94 = 1  
100 / 95 = 1  
100 / 96 = 1  
100 / 97 = 1  
100 / 98 = 1  
100 / 99 = 1  
100 / 100 = 1  

大家发现了什么?我发现很多商数都是大块大块地集中在一起的,而且集中的部分在除数大概为根号n到n之间(多打几个数就会发现)

也就是说这个部分的数字其实可以用一些比较巧妙的部分枚举出来。

所以我就有了一个想法,就这个数据而言,我们可以分两步枚举,第一步是枚举除数1~10,第二步是枚举商1~9来计算,复杂度是根号n

n最大为2的31次方-1, 根号之后是不会超时的

那么第一步直接就暴力就好了,关键是第二步怎么做

通过观察可以 ,发现100 / 1 = 100, 100 / 2 = 50, 100 / 3 = 33

然后在表中除数在100~51商是1,在50~34商是2……

所以我们可以算出“断点”,把除数分成一段一段的,每一段的商数是一样的。

所以我们可以统计每一段的长度,然后乘以商数更新答案

思路大致就是这样

还有一些细节需要注意

(1)枚举的边界问题

如这个数是完全平方数,那么可以除数从1到根号n,商数从1到(根号n) -1

如果不是的话,那么除数是1到根号n,商数也是1到根号n

举个例子可以发现,例如99这个数

根号99为9,在9(根号99)附近时这样的

99 / 9 = 11

99 / 10 = 9

所以如果不是完全平方数的话,两边都要枚举到根号n

(2)当n <= 0 时,要特判,直接输出0

因为按照题目那个程序的话n<=0时循环压根就不会进行,答案不会更新

(3)最后一个断点是根号n

例如

99 / 9 = 11

99 /10 = 9

99 / 11 = 9

99 / 12 = 8

最后一个数9的断点99 / 9 = 11是倒数第二个断点, 而除数到9就到了第一步枚举去了,

所以最后一个断点是9, 最后一段长度为 11 – 9 = 2

代码

#include<cstdio>
#include<cmath>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++) //注意是左闭右开
using namespace std;typedef long long ll;
long long h(int n)
{
ll ans = 0;
int m = sqrt(n + 0.5);
REP(i, 1, m + 1) //第一步枚举除数,直接暴力
ans += n / i;vector<int> g;
int t; //枚举边界问题
if(n % m == 0) t = m;
else t = m + 1;REP(i, 1, m + 1) g.push_back(n / i); //加入“断点”
REP(i, 0, g.size() - 1)
ans += (i + 1) * (g[i] - g[i+1]); //商乘上每一段的长度
ans += g.size() * (g[g.size() - 1] - m); //最后一个断点是根号n return ans;
}int main()
{
int n, T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
if(n <= 0) { puts("0"); continue; } //特判
printf("%lld\n", h(n));
}
return 0;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141691.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:876 阅读:5,464
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,688
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,503
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:731 阅读:4,468
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:5,379
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,263
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站