首页 > 试题广场 >

因数个数和

[编程题]因数个数和
q次询问，每次给一个x，问1到x的因数个数的和。

输入描述:
第一行一个正整数q ；
接下来q行，每行一个正整数 x


输出描述:
共q行，每行一个正整数表示答案
示例1

输入

4
1
2
3
10

输出

1
3
5
27

说明

1的因数有1

2的因数有1,2

3的因数有1,3

以此类推

备注:
1<=q<=10 ,1<= x<=109
算法知识视频讲解
开通博客
头像 重生之我是大菜狗
发表于 2023-07-21 20:47:36
我们枚举x是多少数的因子时，会发现一定是一个数大于sqrt(n),另一个小于sqrt(n) 也就是说x*y可以枚举到，但y*x是枚举不到的， 对于2来说有2*1,2*2,2*3,2*4,2*5......2*n/2 那么对于2出现了n/2对乘式,那么质因子个数为2*n/2也就是x个 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 耕云种月
发表于 2022-07-10 19:18:29
原题解链接：https://ac.nowcoder.com/discuss/149978 首先把因数个数和转化成倍数个数和，即 ∑i=1n⌊ni⌋\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor∑i=1n​⌊in​⌋ 方法1: 利用 ⌊ni⌋\le 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Z_L_G
发表于 2025-08-19 22:04:30
题意 q次询问，每次给一个x，问1到x的因数个数的和 思路 考虑每一个因子的贡献，对于因子p，有x/p对：p(1,2,3,……,n/p)。其中前p-1个是已经被枚举过的，p*p这对被计算了两次，所以每个因子的贡献是(x/p-p)*2+1枚举加和即可 代码 #include<bits/s 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 默默然诶
发表于 2022-08-04 19:08:37
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; int main() { 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

组合数学 枚举
难度：
0条回答 29浏览

热门推荐

通过挑战的用户

查看代码

相关试题

因数个数和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号