牛客练习赛25-A-因数个数和（数学）

本文主要是介绍牛客练习赛25-A-因数个数和（数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://www.nowcoder.com/acm/contest/158/A

题目描述 

q次询问，每次给一个x，问1到x的因数个数的和。

输入描述:

第一行一个正整数q ；
接下来q行，每行一个正整数 x

输出描述:

共q行，每行一个正整数表示答案

示例1

输入

复制

4
1
2
3
10

输出

复制

1
3
5
27

说明

1的因数有12的因数有1,23的因数有1,3以此类推

备注:

1<=q<=10 ,1<= x<=109

思路：1~n 约数的个数的和实际就是看 1~n 在这些数中出现过多少次，例如 1是1~n每个数的因数，所以对1这个因数来说，出现了n/1次，以此类推，然后乘以2（乘以2是因为一个数的因子有i，则n / i也是n的因子）再减去重复计算的，每个数i都有i-1个重复计算了，再减去自己跟自己相乘的情况，合起来就是减去t*t

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,q;
typedef long long int ll;
int main()
{ios::sync_with_stdio(false);cin >> q;while(q--){cin >> n;ll ans = 0, t = sqrt(n);for(int i = 1; i <= t; i++){ans += n / i;}cout<<ans*2-t*t<<endl;}
}

 

这篇关于牛客练习赛25-A-因数个数和（数学）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---