2019年南昌邀请赛网络赛G：tsy's number 莫比乌斯反演

@[toc]

题意

比赛链接
补题链接
，求，模。

思路

参考：walfy，猝s在学ACM的路上，hiarcher

因为：
所以：






令：

现在问题变成了求出，显然这是一个积性函数。
积性函数就是对所有互质的满足的数论函数。
为了能欧拉筛的同时筛出，我们先试着推出。

当时，

为了线性筛出，还需要记录表示的最小质因子的幂。
代码如下：

void init_prime() {
    noprime[0] = noprime[1] = 1;
    mu[1] = 1; phi[1] = 1;g[1] = num[1] = 1;
    for(int i = 2, ret; i < MXN; ++i) {
        if(!noprime[i]) pp[pcnt++] = i, phi[i] = i-1, mu[i] = -1, g[i]=i-2, num[i]=1;
        for(int j = 0; j < pcnt && pp[j] * i < MXN; ++j) {
            ret = i * pp[j];
            noprime[ret] = 1;
            phi[ret] = (pp[j]-1)*phi[i];
            mu[ret] = -mu[i];
            g[ret] = g[i]*g[pp[j]];
            num[ret] = 1;
            if(i % pp[j] == 0) {
                phi[ret] = pp[j]*phi[i];
                mu[ret] = 0;
                num[ret] = num[i] + 1;
                if(num[i] == 1) {
                    if(pp[j] == 2) g[ret] = g[i/pp[j]];
                    else g[ret] = g[i]/(pp[j]-2)*(pp[j]-1)*(pp[j]-1);
                }else g[ret] = g[i] * pp[j];
                break;
            }
        }
    }
    for(int i = 1; i < MXN; ++j) {
        g[i] = g[i-1] + (LL)i * i % mod * i % mod;
        if(g[i] >= mod) g[i] %= mod;
    }
}

对了模数是，结果的式子里面有除2和除3，除2的话用long long直接算就行，3的逆元用欧拉定理算出来是：715827883。

AC_CODE

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
#include <ctime>
#include <iostream>
#include <assert.h>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define fi first
#define se second
#define endl '\n'
#define o2(x) (x)*(x)
#define BASE_MAX 31
#define mk make_pair
#define eb push_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a),(b),sizeof((a)))
#define iis std::ios::sync_with_stdio(false); cin.tie(0)
#define my_unique(x) sort(all(x)),x.erase(unique(all(x)),x.end())
using namespace std;
#pragma optimize("-O3")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> pii;
inline LL read() {
    LL x = 0;int f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x = f ? -x : x;
}
inline void write(LL x, bool f) {
    if (x == 0) {putchar('0'); if(f)putchar('\n');else putchar(' ');return;}
    if (x < 0) {putchar('-');x = -x;}
    static char s[23];
    int l = 0;
    while (x != 0)s[l++] = x % 10 + 48, x /= 10;
    while (l)putchar(s[--l]);
    if(f)putchar('\n');else putchar(' ');
}
int lowbit(int x) { return x & (-x); }
template<class T>T big(const T &a1, const T &a2) { return a1 > a2 ? a1 : a2; }
template<class T>T sml(const T &a1, const T &a2) { return a1 < a2 ? a1 : a2; }
template<typename T, typename ...R>T big(const T &f, const R &...r) { return big(f, big(r...)); }
template<typename T, typename ...R>T sml(const T &f, const R &...r) { return sml(f, sml(r...)); }
void debug_out() { cerr << '\n'; }
template<typename T, typename ...R>void debug_out(const T &f, const R &...r) {cerr << f << " ";debug_out(r...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);
 
 
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int HMOD[] = {1000000009, 1004535809};
const LL BASE[] = {1572872831, 1971536491};
const int mod = 1 << 30;//715827883
const int MOD = 1e9 + 7;//998244353
const int INF = 0x3f3f3f3f;
const int MXN = 1e7 + 7;
const int MXE = 2e6 + 7;
int n, m;
bool noprime[MXN];
int pp[MXN], pcnt;
int num[MXN];
LL g[MXN], inv = 715827883;

void init_prime() {
    noprime[0] = noprime[1] = 1;
    g[1] = num[1] = 1;
    for(int i = 2, ret; i < MXN; ++i) {
        if(!noprime[i]) pp[pcnt++] = i, g[i]=i-2, num[i]=1;
        for(int j = 0; j < pcnt && pp[j] * i < MXN; ++j) {
            ret = i * pp[j];
            noprime[ret] = 1;
            g[ret] = g[i]*g[pp[j]];
            num[ret] = 1;
            if(i % pp[j] == 0) {
                num[ret] = num[i] + 1;
                if(num[i] == 1) {
                    if(pp[j] == 2) g[ret] = g[i/pp[j]];
                    else g[ret] = g[i]/(pp[j]-2)*(pp[j]-1)*(pp[j]-1);
                }else g[ret] = g[i] * pp[j];
                break;
            }
        }
    }
    for(int i = 1; i < MXN; ++i) {
        g[i] = g[i-1] + g[i] * i * i % mod * i % mod;
        if(g[i] >= mod) g[i] %= mod;
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("E://ADpan//in.in", "r", stdin);
    // freopen("E://ADpan//out.out", "w", stdout);
#endif
    init_prime();
    int tim = read();
    while(tim --) {
        n = read();
        LL ans = 0, tmp, ti, ret;
        for(int L = 1, R; L <= n; L = R + 1) {
            ti = n / L;
            R = n / ti;
            ret = (ti*(ti+1)/2)%mod;
            tmp = ti*ret%mod*(ret*(2*ti+1)%mod) % mod * inv % mod;
            ans = (ans + tmp * (g[R] - g[L-1]) % mod) % mod;
        }
        printf("%lld\n", (ans+mod)%mod);
    }
#ifndef ONLINE_JUDGE
    cout << "time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "ms" << endl;
#endif
    return 0;
}