牛客练习赛25A——因数个数和
链接：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的因数有1
2的因数有1,2
3的因数有1,3
以此类推
备注:
1<=q<=10 ,1<= x<=109
又爆零了 垃圾题目
把求因数个数转换成求倍数个数 比如1到9这个区间里，1作为因数的就出现了9/1 9次 2作为因数就出现了9/2 4次 这样最后其实就是求出y=n/x 这个函数从1到n的离散值，好多博客都讲得不清楚这个对称，乱抄一通，这里求1到sqrt(n)之后能直接乘2的原因是 虽然1-sqrt(n) 和sqrt(n)到n这两个区间的函数值不同，但是比如2在1-sqrt(n)这里区间里，通过n/2得到的这个函数值其实刚好是sqrt(n)到n这个区间里的自变量 也就是两个区间的x和y是相反的
而不是一句什么狗屁对称就带过
然后减去sqrt(n)*sqrt(n)是因为里面有一些比如9/3=3 这其实只能算一个 但是*2之后就算了两次，然后我还是不懂他妈的为什么要sqrt(n)*sqrt(n) 真是垃圾题目
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100];
int main(){
ll n;
int t;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
long long x = sqrt(n);
long long ans = 0;
for(long long i = 1;i <= x; ++i){
ans += n / i;
}
ans = 2*ans - x*x;
printf("%lld\n",ans);
}
}
