ICPC2017 Urumqi

题目描述

Consider a triangle of integers, denoted by T. The value at (r, c) is denoted by Tr,c , where 1 ≤ r and 1 ≤ c ≤ r. If the greatest common divisor of r and c is exactly 1, Tr,c = c, or 0 otherwise.
Now, we have another triangle of integers, denoted by S. The value at (r, c) is denoted by S r,c , where 1 ≤ r and 1 ≤ c ≤ r. S r,c is defined as the summation    
Here comes your turn. For given positive integer k, you need to calculate the summation of elements in k-th row of the triangle S.

输入

The first line of input contains an integer t (1 ≤ t ≤ 10000) which is the number of test cases.
Each test case includes a single line with an integer k described as above satisfying 2 ≤ k ≤ 10^8 .

输出

For each case, calculate the summation of elements in the k-th row of S, and output the remainder when it divided
by 998244353.

样例输入

2
2
3

样例输出

1
5

所有与k不互质的数的贡献就是p1的倍数的贡献+p2的倍数的贡献+...+pu的倍数的贡献-p1*p2的倍数的贡献-p1*p3的倍数的贡献-...+p1*p2*p3的倍数的贡献+......

以p1的倍数的贡献为例，他的贡献是(p1*1)^2+(p1*2)^2+...+(p1*[k/p1])^2，就是p^2*(1^2+2^2+...+(p1*[k/p1])^2

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+10;
const int p=998244353;
int T,cnt,k;
bool vis[N];
int prime[N],a[N];
void pre()
{
    for (int i=2;i<N;i++)
    {
        if (!vis[i]) prime[++cnt]=i;
        for (int j=1;j<=cnt&&prime[j]*i<N;j++)
        {
            vis[prime[j]*i]=1;
            if (i%prime[j]==0) break;
        }

    }
}
ll poww(ll x,int y)
{
    ll ret=1;
    while (y)
    {
        if (y&1) ret=ret*x%p;
        x=x*x%p;
        y>>=1;
    }
    return ret;
}
int fund(int n)
{
    int sum=0;
    for (int i=1;i<=cnt;i++)
    {
        if (prime[i]>n) break;

        if (n%prime[i]==0)
        {
            a[sum++]=prime[i];
            while (n%prime[i]==0) n/=prime[i];
        }
    }
    if (n>1) a[sum++]=n;
    return sum;
}
void solve(int n)
{
    ll nn=(ll)n;
    ll inv6=poww(6,p-2);
    ll ans=nn%p*(nn+1)%p*(2*nn+1)%p*inv6%p;

    int sum=fund(n);

    ll tmp=0;
    for (int i=1;i<(1<<sum);i++)
    {
        ll x=1;int s=0;
        for (int j=0;j<sum;j++)
        {
            if ((i>>j)&1)
            {
                x=x*(ll)a[j]%p;
                s++;
            }
        }

        ll t=(ll)n/x;
        if (s&1) tmp=(tmp+x*x%p*t%p*(t+1)%p*(2*t+1)%p*inv6%p)%p;
        else tmp=((tmp-x*x%p*t%p*(t+1)%p*(2*t+1)%p*inv6%p)%p+p)%p;

    }

    ans=((ans-tmp)%p+p)%p;

    printf("%lld
",ans);
}
int main()
{
    pre();
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&k);
        solve(k);
    }
    return 0;
}