Luogu4449 于神之怒加强版

发表于 分类于 ， ， 阅读次数：

题意：给定 ，求

答案对 取模，多组数据，，，其中 是定值，时限 。

回忆“反演动机”的核心思想：用 拆解 。

根据这个思想，对于任意数论函数 ，我们构造数论函数 满足 ，则可以用 来拆解

回到本题，我们构造 满足 ，即 ，则

当 时， 恰好是 ，于是这种拆解 的手法也被称为“欧拉反演”，其实本质还是卷 。

需用一般化的线性筛求出，具体细节不述。复杂度 。

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
#include <algorithm>
#include <cstdio>

const int MaxN = 5e6+5, mod = 1000000007;

int powM(int a, int t) {
    int ans = 1;
    while(t) {
        if (t&1)
            ans = 1ll*ans*a %mod;
        a = 1ll*a*a %mod;
        t >>= 1;
    }
    return ans;
}

int p[MaxN/5], pk[MaxN/5], totP, F[MaxN];
bool flag[MaxN];

void sieve(int n, int k) {
    F[1] = 1;
    for (int i=2; i<=n; i++){
        if (!flag[i]) {
            p[++totP] = i;
            pk[totP] = powM(i,k);
            F[i] = pk[totP]-1;
        }
        for (int j=1; j<=totP; j++) {
            int t = i*p[j];
            if (t>n) break;
            F[t] = 1ll*F[i]*(i%p[j]==0 ? pk[j] : F[p[j]]) %mod;
            flag[t] = true;
            if (i%p[j]==0)break;
        }
    }
    for (int i=1; i<=n; i++)
        F[i] = (F[i-1]+F[i]) %mod;
}

int calc(int n, int m) {
    int ans = 0, l = 1;
    while(l <= std::min(n, m)) {
        int r = std::min(n/(n/l), m/(m/l));
        ans = (ans + 1ll*(n/l)*(m/l)%mod*(F[r]-F[l-1])) %mod;
        l = r+1;
    }
    return (ans+mod)%mod;
}

int main() {
    int T, K;
    scanf("%d%d", &T, &K);
    sieve(5e6, K);
    
    while(T--) {
        int N, M;
        scanf("%d%d", &N, &M);
        printf("%d\n", calc(N, M));
    }
    return 0;
}