首先看这道题目，我预感商数肯定是有规律的排列的，于是我打表找一下规律
100 / 1 = 100100 / 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#include #include #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 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;}