题目传送门

题目大意

求

解题思路

欧拉函数有一条性质
一个整数可以表示为
因为欧拉函数是积性函数，所以
上下约分后
同理
所以原式等于
枚举，原式
用换个元
交换一下枚举顺序
最右边求个和，用其中
所以最右边记作
原式变为
令
交换一下枚举顺序，原式变为
合并一下

中间部分是一个迪利克雷卷积的形式，是个显然可以看作一个积性函数，可以用欧拉筛来处理
则
其中是个质数，是个正整数
可以用开头讲的欧拉函数的性质证明
所以最后用欧拉筛预处理出函数的每个子，再整除分块处理即可
另外需要注意，显然不是个质数，不可以直接对求逆，可以先除以之后对求逆

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 1 << 30;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 1e7 + 10;
int prime[maxn], tot;
bool notprime[maxn];
ll fun[maxn];
ll inv3 = 715827883;
void init()
{
    fun[1] = 1;
    for (ll i = 2; i < maxn; ++i)
    {
        if(!notprime[i])
        {
            prime[tot++] = i;
            fun[i] = i - 2;
        }
        for (int j = 0; j < tot && i * prime[j] < maxn; ++j)
        {
            notprime[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                if ((i / prime[j]) % prime[j] == 0)
                {
                    fun[i * prime[j]] = fun[i] * prime[j];
                }else
                {
                    if (prime[j] == 2)
                    {
                        fun[i * prime[j]] = fun[i / prime[j]];
                    }else
                    {
                        fun[i * prime[j]] = fun[i] / (prime[j] - 2) * (prime[j] - 1) * (prime[j] - 1);
                    }
                }
                break;
            }
            fun[i * prime[j]] = fun[i] * fun[prime[j]];
        }
    }
    for (int i = 1; i < maxn; ++i)
        fun[i] = (fun[i - 1] + fun[i] * i % mod * i % mod * i % mod) % mod;
}

ll sum(ll t)
{
    ll ret = t * (t + 1) / 2;
    return ret * ret % mod * t % mod * (2 * t % mod + 1) % mod * inv3 % mod;
}

ll cal(int n)
{
    ll res = 0;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        (res += (fun[r] - fun[l - 1] + mod) % mod * sum(n / l) % mod) %= mod;
    }
    return res;
}

int main()
{
    init();
    int t;
    int n;
    for (read(t); t--;)
    {
        read(n);
        printf("%lld\n", cal(n));
    }
}