刷题康复训练261115(数学)
- 2026-11-16 20:18:25
刷题康复训练261115(数学)BLG夺冠了,熬夜看的我心潮澎湃,没想到当初做梦般一穿四LCK真的实现了 
有段时间没做题了,今天简单一道数学相关的题目 

O(n)复杂度的就不赘述了,就是从小到大枚举,主要讲一下复杂度更小的方法。 这题的突破口在因子的对称性:i 是 n 的因子的话,n/i 也是,而且这两个数一个在 √n 以下一个在 √n 以上,因子总是成对出现,隔着 √n 相望。所以想拿全所有因子,枚举到 √n 就够了,剩下的另一半是照着已枚举的因子的影子,白送的。 具体数法分两段。第一段 d 从 1 走到 √n,遇到因子就计数,这是小因子的升序。第一段走完后,第二段让 d 从 √n 倒着走回 1,再遇到因子就返回 n/d——d 越小 n/d 越大,出来的正好是大因子的降序,接在第一段后面,整体就是全因子的升序。全程不用存列表,只要第 k 个,一个计数器边数边判,数到就直接返回。 拿 n=12 对一下:√12 不到 4,第一段数到 1、2、3,第二段 d=3、2、1 对应 4、6、12,拼起来 [1,2,3,4,6,12],是对的。 有一个地方容易栽:完全平方数。n=4 时 d=2 满足 dd==n,这个因子在第一段已经数过一次了,第二段倒着走回来它又会以 n/d 的身份冒出来,不跳过的话第 k 个就整体错一位。写的时候要加一行判断,dd 等于 n 就跳过,这是这题唯一称得上坑的地方。 复杂度:时间 O(√n),两段循环都走 √n;空间 O(1)



classSolution{public:int kthFactor(int n, int k) {int d;for(d = 1; d * d <= n; d++)if(n % d == 0 && --k == 0) return d;for(d--; d >= 1; d--) {if(d * d == n) continue;if(n % d == 0 && --k == 0) return n / d;}return -1;}};
本文来自网友投稿或网络内容,如有侵犯您的权益请联系我们删除,联系邮箱:wyl860211@qq.com 。