tsy’s number

标签： 数学 莫比乌斯反演

---

tsy’s number

标签： 数学 莫比乌斯反演

---

题目描述

Tsy as a math enthusiast and the favorite thing is to get the sum of function, one day he was studying the Euler function, while writing a formula
$$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\frac{\varphi (i)\varphi (j^2)\varphi (k^3)}{\varphi (i)\varphi (j)\varphi (k)}\varphi (gcd(i,j,k))$$
After had written,tsy took it to his friend zxy for solution but zxy Zxy don’t know any Math at all. As the friends of Zxy, can you help him ？

the result need to 2^30modulo

Input

multiple testcase
a single T in the first line represents the number of groups (T≤10000)and T lines follows each line has a number n(1≤n≤10^7)

Output

For each set of data, output a number to represent the result

Examples

样例输入
3
2
4
6
样例输出
30
1291
12715

题解

看到$\sum $和$gcd$很容易联想到莫比乌斯反演。第一步还是先化简式子:
根据唯一分解定理:$n=p_{1}^{k1}p_{2}^{k2}…p_{m}^{km}$和欧拉函数的性质，可得
$\varphi (n)=\prod_{i=1}^{m}(p_{i}-1)p^{ki-1}$
$\varphi (n^2)=\prod_{i=1}^{m}(p_{i}-1)p^{2ki-1}$
$\varphi (n^3)=\prod_{i=1}^{m}(p_{i}-1)p^{3ki-1}$
则原式化简为:
$$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}j\ast k^2\ast \varphi (gcd(i,j,k))$$
老套路，我们枚举$gcd$,则
$$\sum_{x=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}j\ast k^2\ast \varphi (x)[gcd(i,j,k)==x]$$
将$\varphi (x)$提前，则:
$$\sum_{x=1}^{n}\varphi (x)\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}j\ast k^2\ast [gcd(i,j,k)==x]$$
化简到这里我们就比较熟悉了，我们设以下函数:
$$f(x)=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}j\ast k^2\ast [gcd(i,j,k)==x]$$
$$F(x)=\sum_{x|d}f(d)=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}j\ast k^2\ast [x|gcd(i,j,k)]$$
更换枚举项，枚举x的倍数，则
$$F(x)=x^3\ast a\ast \frac{a\ast (a+1)}{2}\frac{a\ast (a+1)\ast (2a+1)}{6}$$
其中$a=\frac{n}{x}$
于是:
$$Ans=\sum_{x=1}^{n}\varphi (x)f(x)=\sum_{x=1}^{n}\varphi (x)\sum_{x|d}u(\frac{d}{x})F(d)$$
考虑枚举x的倍数，则
$$Ans=\sum_{d=1}^{n}d^3\ast a\ast \frac{a\ast (a+1)}{2}\frac{a\ast (a+1)\ast (2a+1)}{6}\sum_{x|d}\varphi (x)u(\frac{d}{x})$$
其中$a=\frac{n}{d}$
不妨设$g(a)=a\ast \frac{a\ast (a+1)}{2}\frac{a\ast (a+1)\ast (2a+1)}{6}$
那么原式为:
$$\sum_{d=1}^{n}d^3g(\left \lfloor \frac{n}{d} \right \rfloor)\sum_{x|d}\varphi (x)u(\frac{d}{x})$$
后面的和式我们可以预处理，函数$g$我们也可以预处理,最后用数论分块就可以完成这道题啦
PS：对于和式$\sum_{x|d}\varphi (x)u(\frac{d}{x})$我们需要用线性筛，用暴力的埃式筛法会T…
这里推荐一篇很好的线性筛积性函数博客
最后感谢王大佬的对我在此题的指点（考试中敢开这道题还A了的人，我除了%还能干什么…）

代码

#include<bits/stdc++.h>
#define N 10000020
#define ll long long 
#define debug system("pause") 
using namespace std;
const ll p = (1 << 30);

int t, n, cnt = 0;
int pri[N], low[N];
ll g[N], h[N]; 
bool vis[N];

void get()
{
    h[1] = 1;
    int t = N - 10;
    for(int i = 2; i <= t; i ++)
    {
        if(!vis[i])
        {
            h[i] = i - 2; low[i] = i; 
            pri[++ cnt] = i;
        }
        for(int j = 1; j <= cnt && i * pri[j] <= t; j ++)
        {
            vis[i * pri[j]] = true;
            if(i % pri[j] == 0)
            {
                low[i * pri[j]] = low[i] * pri[j];
                if(i == low[i]) 
                {
                    if(i == pri[j]) h[i * pri[j]] = h[i] * pri[j] + 1;
                    else h[i * pri[j]] = h[i] * pri[j];
                    low[i] *= pri[j];
                }
                else h[i * pri[j]] = h[i / low[i]] * h[low[i] * pri[j]];
                break; 
            }
            else h[i * pri[j]] = h[i] * h[pri[j]], low[i * pri[j]] = pri[j];
        }
    }
    for(int i = 1; i <= t; i ++)
    {
        h[i] = h[i] * ((((i * i) % p) * i) % p);
        h[i] %= p;
    }
    for(int i = 1; i <= t; i ++)
        h[i] = (h[i] + h[i - 1]) % p;
    ll x = 0, y = 0, z = 0;
    for(int i = 1; i <= t; i ++)
    {
        x += 1; y += i; z += i * i;
        x %= p; y %= p; z %= p;
        g[i] = (((x * y) % p) * z) % p;
    }
}

int main()
{
    get(); 
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d", &n);
        ll ans = 0;
        for(int l = 1, r; l <= n; l = r + 1)
        {
            r = n / (n / l);
            ans = ans + (g[n / l] * (h[r] - h[l - 1] + p) % p);
            ans %= p; 
        }
        printf("%lld\n", ans % p);
    }
    return 0;
}