View Code of Problem 3641

#include <cstdio>
#include <algorithm>
#define sc scanf
#define pr printf
using namespace std;
const int N = 1000005;
const int mod = 258280327;
int T,n = N-4,i,j,k,tot,F,ans;
int prime[N],p[N],sum[N],g[N],Sum[N] ;

int main() {
    for(i=2; i<=n; ++i) {
        if(!p[i])prime[++tot]=p[i]=i;
        for(j=1; j<=tot&&prime[j]<=p[i]&&prime[j]<=n/i; ++j)p[i*prime[j]]=prime[j];
    }
    g[1]=1;
    for(i=2; i<=n; ++i)
        if(p[i]==p[i/p[i]])g[i]=g[i/p[i]];
        else {
            g[i]=g[i/p[i]]<<1;
            g[i]%=mod;
        }
    for(i=1; i<=n; ++i)
        for(j=i+i,k=1; j<=n; j+=i,++k) {
            sum[j]=(g[k]+sum[j])%mod;
        }
    for(i=1; i<=n; ++i) {
        F=(F+i*2-1-sum[i-1]+mod)%mod;
        Sum[i]=(Sum[i-1]+F)%mod;
    }
    scanf("%d",&T);
    while(T--) {
        sc("%d",&n);
        pr("%d\n",Sum[n]);
    }
}