Sum of the Line

标签： 莫比乌斯反演 数学

---

题目描述

戳这里
大意就是给你一个$n$，求在小于$n$里面与$n$互质的数的平方和是多少,即:

$$\sum_{i=1}^{n}i^{2}[gcd(n,i)==1]$$

题解

比赛的时候和队友讨论出容斥的做法，不过想着是$2^p$的复杂度感觉不可行。结果没分析到在$1e8$内一个数的质因数不会超过9个。直接暴力枚举即可。
这里提供在wsy大佬以及Acoder的博客点拨下提供一种新的做法：莫比乌斯反演
我们设:

$$f(x)=\sum_{i=1}^{n}i^{2}[gcd(n,i)==1]$$

$$F(x)=\sum_{x|d}f(d)=\sum_{i=1}^{n}i^2[x|gcd(n,i)]$$

则：

$$Ans=f(1)=\sum_{d=1}^{n}u(d)F(d)$$

把$F(d)$展开后

$$Ans=\sum_{d|n}u(d)\sum_{i=1}^{\frac{n}{d}}(i*d)^2$$

把后面的和式展开后化简得:

$$\frac{n}{6}[2n\sum_{d|n}u(d)\frac{n}{d}+3n\sum_{d|n}u(d)+\sum_{d|n}u(d)d]$$

而$\sum_{d|n}u(d)\frac{n}{d}=\varphi (n)$, $\sum_{d|n}u(d)d$是一个积性函数，按照定义求即可

代码

#include<bits/stdc++.h>
#define N 100010
#define ll long long
using namespace std;

const ll p = 998244353;
int t, n, cnt = 0;

ll pow_mul(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

ll phi(ll x)
{
    ll ans = x;
    for(ll c = 2; c * c <= x; c ++)
    {
        if(x % c == 0) ans -= ans / c;
        while(x % c == 0) x /= c;
    }
    if(x > 1) ans -= ans / x;
    return ans;
}

ll calc(ll x)
{
    ll a1 = (x == 1), a2 = 1;
    for(ll c = 2; c * c <= x; c ++)
    {
        if(x % c == 0) a2 = a2 * (1 - c + p) % p;
        while(x % c == 0) x /= c;
    }
    if(x > 1) a2 = a2 * (1 - x + p) % p;
    return (((3 * n % p) * a1 % p) + a2) % p;
}

int main()
{
    scanf("%d", &t);
    ll inv = pow_mul(6, p - 2);
    while(t --)
    {
        scanf("%d", &n);
        ll t = n * inv % p;
        ll ans = (2 * n % p) * phi(n) % p;
        // printf("%lld", ans); system("pause");
        ans = (ans + calc(n)) % p;
        // printf("%lld", ans); system("pause");
        ans = ans * t % p;
        printf("%lld\n", ans);
    }
    return 0;
}

心得

会数论的人就是可以为所欲为 orz