题目大意

雅礼考反演考疯了。。

定义函数 $c(n)$ 表示 n 的质因子的数量 定义函数 $g(n) = −1^{c(n)}$ 定义函数 $h(n) = ∑_{d|n}d$，即 $n$ 所有约数的总和. 定义函数 $f(n) = ∑_{d|n}g(d) \times h(n/d)$，即 $g$与 $h$ 的卷积. 定义函数 $F(n) = ∑_{i=1}^n f(i)$，即 $f$ 的前缀和. 对于给定的 $n$ ，求 $F(n)\ \text{mod}\ 998244353$ 的值

$1\leq n\leq 10^{18}$

多组询问，询问数不超过20

题解

我们注意到

$$ f=1*g*id $$

由于狄利克雷卷积的结合律我们可以把$1*g$结合到一起

然后我们考虑一下$1*g$的性质

$(1*g)(n)=[n是完全平方数]$

（证明以后再补）

然后就可以这样

$$ F(n)=\sum_{i=1}^n\sum_{d|i}\frac i d[i是完全平方数]\
$$

然后我们变换求和指标，枚举$d^2$，从而消去一个判断

$$ \sum_{i=1}^n\sum_{d^2|i}\frac i {d^2} $$

我们令$\frac i {d^2}=k$，考虑如何计算贡献，对于一个确定的$d$，它的贡献体现在$d^2,2d^2\cdots,kd^2$，即它的所有倍数上，贡献值依次为$1,2,\cdots k$，这部分可以用等差数列求和公式$O(1)$求

我们可以先枚举$d$然后枚举$d^2$的所有倍数，统计贡献

$$ \sum_{d=1}^\sqrt n\sum_{i=1}^{\lfloor\frac n {d^2}\rfloor}i $$

用下面的式子计算，复杂度是$O(\sqrt n)$

过不去

注意到$\lfloor\frac n {d^2}\rfloor$是可以分块求的

然后就可以将复杂度化成$O(^4\sqrt n)$（不知道为啥题解上是三次根号，可能是我太菜分析错了）

代码

并没有测试过，可能（肯定）有锅

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
const ll mod = 998244353;
const ll inv2 = 499122177;
inline ll mmod(ll x)
{
    x %= mod;
    x += mod;
    return x % mod;
}
inline ll msqrt(ll x)
{
    ll ans = sqrt((ldb)x);
    return ans;
}
ll cal(ll n)
{
    ll x = msqrt(n), ans = 0;
    for (ll i = 1, lst; i <= x; i = lst + 1)
    {
        ll tmp = n / i / i;
        lst = msqrt(n / tmp);
        ans = mmod(ans + mmod(mmod(tmp * (tmp + 1)) * (lst - i + 1)));
    }
    ans = mmod(ans * inv2);
    return ans;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        cout << cal(n) << endl;
    }
}

由于我太菜，公式可能会打错，如果你发现了错误，请联系我以修正