思路

数论分块模板,式子res=(res+n/i)的i枚举时会超时,注意到n/i的结果会有连续的一段相等,我们使用数论分块,直接返回每一段的答案。 对于常数n,使得式子[ni]=[nj][\frac{n}{i}]=[\frac{n}{j}]成立的最大的满足的ijnj[n[ni]]i\le j\le n的j的值为[\frac{n}{[\frac{n}{i}]}],即[ni][\frac{n}{i}]所在的块的右端点为[n[ni]][\frac{n}{[\frac{n}{i}]}]

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

int H(int n){
	int res=0,l=1,r;
	while(l<=n){
		r=n/(n/l);
		res+=(r-l+1)*(n/l);
		l=r+1;
	}
	return res;
}


signed main(){
	int t,n;
	cin>>t;
	while(t--){
		cin>>n;
		cout<<H(n)<<"\n";
	}
	return 0;
}