题解 | #日常诈骗签到题#

jzgg原先的压轴，结果不小心爆了。。。
首先这个题的标准做法就是数论
这里给出推理过程：
即代码为

#include<iostream>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int main(){
    ll n,m;
    cin>>n;
    while(n--){
        cin>>m;
        cout<<m*(m+1)/2%mod<<"\n";
    }
}

在赛前给出的标程是采用整除分块，欧拉函数筛计算

#include<iostream>
using namespace std;
const int N=1e6+7;
const int mod=1e9+7;
typedef long long ll;
ll su[N],phi[N];
void oula(){
    phi[1]=1;
    for(int i=2;i<N;i++){
        if(!phi[i])su[++su[0]]=i,phi[i]=i-1;
        for(int j=1;j<=su[0]&&i*su[j]<N;j++){
            if(i%su[j]==0){
                phi[i*su[j]]=phi[i]*su[j]
                break;
            }
            phi[i*su[j]]=phi[i]*(su[j]-1);
        }
        phi[i]=(phi[i]+phi[i-1])%mod;
    }
}
int main(){
    oula();
    int T;
    cin>>T;
    for(int j=1;j<=T;j++){
        ll n,sum=0;
        cin>>n;
        for(int i=1,r;i<=n;i=r+1){
            r=n/(n/i);
            sum=(sum+(n/i)*(phi[r]-phi[i-1]+mod)%mod)%mod;
        }
        cout<<sum<<"\n";
    }
}