超时的看我

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,cnt;
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cnt+=n/i;
    }
    cout<<cnt;
    return 0;
}

这是正确代码，而你们的有可能是这样：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,cnt;
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        ll sum=0;
        for(ll j=1;j<=i;j++){
            if(i%j==0)sum++;
        }
        cnt+=sum;
    }
    cout<<cnt;
    return 0;
}

那么有什么方法可以令时间复杂度变小呢？
有的！！！！！(>_O!!!!

对于一个数i，如果j是i的因数，那么i/j也是i的因数。因此，我们只需要遍历到√i即可，因为大于√i的因
数可以通过小于√i的因数直接计算出来。

还有一大原因！！！！

对于每个数j（1到n），它会作为因数出现在所有j的倍数中。因此，可以直接统计每个j作为因数出现的
次数，而不需要逐个判断！！！！

你看懂了吗！！！

对你有帮助的话就点个关注吧！！！！！！^ U ^)!!!!!!