C++14(g++5.4) 解法, 执行用时: 42ms, 内存消耗: 8300K, 提交时间: 2020-05-23 18:25:09

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,mod=1e9+7,M=1e6;
int ans[N],a[N],n,t;
int main(){
	for(int i=1;i<=M;i++)
		for(int j=i;1LL*i*j<=M;j++){
			 a[i*j]=(i+j)/2;
		} 
	for(int i=1;i<=M;i++) ans[i]=(ans[i-1]+a[i])%mod;
	scanf("%d",&t);	
	while(t--){
		scanf("%d",&n);
		printf("%d\n",ans[n]);
	}
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 306ms, 内存消耗: 42328K, 提交时间: 2020-05-23 19:18:09

l = [0] * 1000005
res = [0] * 1000005

for i in range(1,1001):
    for j in range(i,1000001,i):
        if i * i <= j:
            l[j] = i

for i in range(1,1000001):
    res[i] = res[i-1] + (l[i] + i/l[i]) // 2
    
T = int(input())
for i in range(T):
    num = int(input())
    print(int((res[num]) % (1e9+7)))

C++11(clang++ 3.9) 解法, 执行用时: 35ms, 内存消耗: 4364K, 提交时间: 2020-07-01 14:19:25

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
int V[1000005]={0};
int main()
{
    int i,j,T;
    for(i=1;i<=1e3;i++)
        for(j=i;i*j<=1e6;j++)V[i*j]=i;
	for(i=1;i<=1e6;i++)V[i]=((V[i]+i/V[i])/2+V[i-1])%mod;
	scanf("%d",&T);
	while(T--)scanf("%d",&i),printf("%d\n",V[i]);
    return 0;
}