LibreOJ 6682 梦中的数论

发表于 | 分类于 |

大抵是个十分 trivial 的 Min25 模板题吧（虽然不如简单的函数 trivival）

考虑令 \(T = j+k\)，则题目要求的为 \[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{T=j+1}^{j+n}[(j\mathop{|}i)\land(T\mathop{|}i)]\]

考虑 \(\sum\limits_{j=1}^n\sum\limits_{T=j+1}^{j+n}[(j\mathop{|}i)\land(T\mathop{|}i)]\) 的组合意义，即从 \(i\) 的约数中选无序点对的方案数（当 \(j<T\le i\) 时才可能有贡献）。
故题目所求为 \[\sum\limits_{i=1}^n \binom{\sigma_0(i)}2=\frac12\sum\limits_{i=1}^n(\sigma_0^2(i)-\sigma_0(i))\]

众所周知 \(\sum\limits_{i=1}^n \sigma_0(i) = \sum\limits_{i=1}^n \lfloor\frac ni\rfloor\)，于是 \(O(\sqrt n)\) 求。
\(\sum\limits_{i=1}^n \sigma_0^2(i)\)？直接 Min_25 筛吧。
显然 \(\sigma_0^2(p^c) = (c+1)^2\)。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const long long N = 1e10;
const int MX = 1e5;
const int mod = 998244353;
const int inv = 499122177;
long long n;
int lim;
int vis[MX + 5],prime[MX + 5],cnt;
int tot,le[MX + 5],ge[MX + 5];
long long lis[2 * MX + 5];
int G[2 * MX + 5],Fprime[2 * MX + 5];
int ans;
inline int &id(long long x)
{
    return x <= lim ? le[x] : ge[n / x];
}
int F(int k,long long n)
{
    if(n < prime[k] || n <= 1)
        return 0;
    int ret = (Fprime[id(n)] - 4LL * (k - 1) % mod + mod) % mod;
    for(register int i = k;i <= cnt && (long long)prime[i] * prime[i] <= n;++i)
    {
        long long pw = prime[i],pw2 = (long long)prime[i] * prime[i];
        for(register int c = 1;pw2 <= n;++c,pw = pw2,pw2 *= prime[i])
            ret = (ret + (long long)(c + 1) * (c + 1) % mod * F(i + 1,n / pw) % mod + (long long)(c + 2) * (c + 2) % mod) % mod;
    }
    return ret;
}
int main()
{
    for(register int i = 2;i <= MX;++i)
    {
        if(!vis[i])
            prime[++cnt] = i;
        for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
        }
    }
    scanf("%lld",&n),lim = sqrt(n);
    for(register long long l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        lis[id(n / l) = ++tot] = n / l;
        G[tot] = (n / l % mod - 1 + mod) % mod,ans = (ans - (n / l % mod) * (r - l + 1) % mod + mod) % mod;
    }
    for(register int k = 1;k <= cnt;++k)
    {
        int p = prime[k];
        long long s = (long long)p * p;
        for(register int i = 1;lis[i] >= s;++i)
            G[i] = (G[i] - (G[id(lis[i] / p)] - (k - 1) + mod) % mod + mod) % mod;
    }
    for(register int i = 1;i <= tot;++i)
        Fprime[i] = 4LL * G[i] % mod;
    ans = (long long)(ans + F(1,n) + 1) * inv % mod;
    printf("%d\n",ans);
}