链接:https://ac.nowcoder.com/acm/contest/5678/H
来源:牛客网
 

给出函数的定义如下:
f(x)是所有能够整除 x 的数(包含 1 和 x )中的中位数向下取整的大小,
g(x)=∑i=1xf(i)g(x)=\sum_{i = 1}^{x}{f(i)}g(x)=∑i=1x​f(i)

输入描述:

输入包含多组数据,第一行为一个数字 T(1≤T≤10)T(1 \le T \le 10)T(1≤T≤10) ,表示测试数据组数。
接下来是 T 组数据,每组数据为一行,包含一个整数 x(1≤x≤1000000)x(1 \le x \le1000000)x(1≤x≤1000000)

输出描述:


 

每组数据输出包含一个整数,表示 g(x) 的值,结果要求对 1e9+7 取模。

示例1

输入

复制3 1 2 3

3
1
2
3

输出

复制1 2 4

1
2
4

说明

能够整除 1 的数字有 1 ,故 f(1)=1;
能够整除 2 的数字有 1,2 所以中位数为⌊1+22⌋=1\lfloor \frac{1+2}{2} \rfloor = 1⌊21+2​⌋=1,故 f(2) = 1;
能够整除 3 的数字有 1,3 ,所以中位数为1+32=2\frac{1+3}{2}=221+3​=2 ,故 f(3) = 2;
从而得出 g(1) = 1,g(2) = 2,g(3) = 4 。

示例2

输入

复制1 1000000

1
1000000

输出

复制677045223

677045223

代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
#define ll long long
#define lb long double
#define INF 0x3f3f3f3f
#define maxn 200010
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
ll n,s,m,k,t,sum;
ll mod=1e9+7;
ll a[1000001],b[1000001],c[1000001];
int main()
{
    cin>>t;
    b[0]=0;
    for(int i=1;i<=1000;i++)
    {
        for(int j=i;j<=1000000;j+=i)
        {
            if(c[j]*c[j]>=j)
            continue;
            c[j]=i;
        }
    }
    for(int i=1;i<=1000000;i++)
    {
        a[i]=floor((c[i]+i/c[i])*1.0/2);
        b[i]=b[i-1]+a[i]%mod;
        b[i]%=mod;
    }
    while(t--)
    {
        cin>>n;
        printf("%lld\n",b[n]);
    }
     
}