牛客练习赛25 因数个数和

因数个数和

题意: q次询问，每次给一个x(1e9)，问1到x的因数个数的和。

思路:很明显sqrt(x)算法.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll work(int n){
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(i%j==0)  ans++;
        }
    }
    return ans;
}
int main(){
//    for(n=1;n<=10;n++){
////        cout <<n<<"->"<<work(n)<<endl;
//        cout <<work(n)<<",";
//    }
    int T;
    cin >>T;
    while(T--){
        cin >> n;
        ll ans=0;
        int y=sqrt(n);
        for(int i=1;i<=sqrt(n);++i){
            ans+=n/i;
        }
        cout << ans*2-y*y << endl;
    }
}