链接: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);
    }
}