数论求和题型整理_代码

数论求和题型整理_代码

对应：数论求和题型整理

每道题保留一个完整代码块；题型推导统一放在正文笔记中。

公共模板直接省略实现，例如 read()、普通线性筛 sieve()、快速幂 qpow() 等；

题目真正新增的预处理、算术函数、数据结构与 calc2() 完整保留。

0. 公共实现

0.1 线性筛：μ,φ\mu,\varphi

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
int pri[maxn], pcnt;
bool isp[maxn];
ll phi[maxn];
int mu[maxn];

void sieve( int N ) {
    pcnt = 0;
    fill( isp, isp + N + 1, true );
    isp[0] = isp[1] = false;
    phi[1] = 1, mu[1] = 1;
    for( int i = 2; i <= N; ++ i ) {
        if( isp[i] ) {
            pri[++ pcnt] = i;
            phi[i] = i - 1;
            mu[i] = -1;
        }
        for( int j = 1; j <= pcnt && 1LL * i * pri[j] <= N; ++ j ) {
            int p = pri[j];
            isp[i * p] = false;
            if( i % p == 0 ) {
                phi[i * p] = phi[i] * p;
                mu[i * p] = 0;
                break;
            }
            phi[i * p] = phi[i] * ( p - 1 );
            mu[i * p] = -mu[i];
        }
    }
}

0.2 前缀和

1
2
3
4
5
6
7
8
9
10
11
ll pre_mu[maxn];
ll pre_phi[maxn];

void init( int N ) {
    sieve( N );

    for( int i = 1; i <= N; ++ i ) {
        pre_mu[i] = pre_mu[i - 1] + mu[i];
        pre_phi[i] = pre_phi[i - 1] + phi[i];
    }
}

0.3 二维整除分块

这一类题的 calc2() 基本只有“区间系数”不同。

1
2
3
4
5
6
7
8
9
10
11
ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        // res += 区间 [l,r] 的算术函数和 × 当前整除商贡献
    }
    return res;
}

一、互质计数与固定 GCD

Q1 P2158 仪仗队

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 3e5 + 5;

ll read( ) { /* 模板代码略 */ }

int pri[maxn], pcnt;
bool isp[maxn];
ll phi[maxn];
int mu[maxn];
void sieve( int N ) { /* 模板代码略 */ }

ll pre_mu[maxn];
ll pre_phi[maxn];

void init( int N ) {
    sieve( N );
    for( int i = 1; i <= N; ++ i ) {
        pre_mu[i] = pre_mu[i - 1] + mu[i];
        pre_phi[i] = pre_phi[i - 1] + phi[i];
    }
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        res += ( pre_mu[r] - pre_mu[l - 1] ) * vn * vm;
    }
    return res;
}

void solve( ) {
    int n = read( );
    if( n == 1 ) cout << 0 << '\n';
    else cout << calc2( n - 1, n - 1 ) + 2 << '\n';
}

int main( ) {
    init( maxn - 1 );
    solve( );
    return 0;
}

Q2 P3455 ZAP-Queries

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 3e5 + 5;

ll read( ) { /* 模板代码略 */ }

int pri[maxn], pcnt;
bool isp[maxn];
ll phi[maxn];
int mu[maxn];
void sieve( int N ) { /* 模板代码略 */ }

ll pre_mu[maxn];
ll pre_phi[maxn];

void init( int N ) {
    sieve( N );
    for( int i = 1; i <= N; ++ i ) {
        pre_mu[i] = pre_mu[i - 1] + mu[i];
        pre_phi[i] = pre_phi[i - 1] + phi[i];
    }
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        res += ( pre_mu[r] - pre_mu[l - 1] ) * vn * vm;
    }
    return res;
}

void solve( ) {
    int n = read( ), m = read( ), k = read( );
    cout << calc2( n, m, k ) << '\n';
}

int main( ) {
    init( maxn - 1 );
    int T = read( );
    while( T -- ) solve( );
    return 0;
}

Q3 P2522 Problem b

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 3e5 + 5;

ll read( ) { /* 模板代码略 */ }

int pri[maxn], pcnt;
bool isp[maxn];
ll phi[maxn];
int mu[maxn];
void sieve( int N ) { /* 模板代码略 */ }

ll pre_mu[maxn];
ll pre_phi[maxn];

void init( int N ) {
    sieve( N );
    for( int i = 1; i <= N; ++ i ) {
        pre_mu[i] = pre_mu[i - 1] + mu[i];
        pre_phi[i] = pre_phi[i - 1] + phi[i];
    }
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        res += ( pre_mu[r] - pre_mu[l - 1] ) * vn * vm;
    }
    return res;
}

void solve( ) {
    int a = read( ), b = read( ), c = read( ), d = read( );
    int k = read( );
    ll res = calc2( b, d, k ) - calc2( a - 1, d, k ) 
           - calc2( b, c - 1, k ) + calc2( a - 1, c - 1, k );
    cout << res << '\n';
}

int main( ) {
    init( maxn - 1 );
    int T = read( );
    while( T -- ) solve( );
    return 0;
}

二、GCD 满足某种性质

Q4 P2568 GCD

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e7 + 5;

ll read( ) { /* 模板代码略 */ }

int pri[maxn / 10], pcnt;
bool isp[maxn];
int mu[maxn];
void sieve( int N ) { /* 模板代码略 */ }

ll pre_mu[maxn];
// ll pre_phi[maxn];

void init( int N ) {
    sieve( N );
    for( int i = 1; i <= N; ++ i ) {
        pre_mu[i] = pre_mu[i - 1] + mu[i];
        // pre_phi[i] = pre_phi[i - 1] + phi[i];
    }
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        res += ( pre_mu[r] - pre_mu[l - 1] ) * vn * vm;
    }
    return res;
}

void solve( ) {
    int n = read( );
    ll ans = 0;
    for( int i = 1; i <= pcnt && pri[i] <= n; ++ i ) {
        ans += calc2( n, n, pri[i] );
    }
    cout << ans << '\n';
}

int main( ) {
    init( maxn - 1 );
    solve( );
    return 0;
}

Q5 P2257 YY 的 GCD

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e7 + 5;

ll read( ) { /* 模板代码略 */ }

int pri[maxn / 10], pcnt;
bool isp[maxn];
int mu[maxn];
void sieve( int N ) { /* 模板代码略 */ }

ll g[maxn], pre_g[maxn];

void init( int N ) {
    sieve( N );
    for( int i = 1; i <= pcnt; ++ i ) {
        int p = pri[i];
        for( int t = p; t <= N; t += p ) {
            g[t] += mu[t / p];
        }
    }
    for( int i = 1; i <= N; ++ i ) {
        pre_g[i] = pre_g[i - 1] + g[i];
    }
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        res += ( pre_g[r] - pre_g[l - 1] ) * vn * vm;
    }
    return res;
}

void solve( ) {
    int n = read( ), m = read( );
    cout << calc2( n, m ) << '\n';
}

int main( ) {
    init( maxn - 1 );
    int T = read( );
    while( T -- ) solve( );
    return 0;
}

三、对 GCD 赋权

Q6 P2303 Longge 的问题

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e6 + 5;

ll read( ) { /* 模板代码略 */ }

ll phi( ll n ) {
    ll res = n;
    for( ll i = 2; i <= n / i; ++ i ) {
        if( n % i == 0 ) {
            res = res / i * ( i - 1 );
            while( n % i == 0 ) n /= i;
        }
    }
    if( n > 1 ) res = res / n * ( n - 1 );
    return res;
}

void solve( ) {
    ll n = read( );
    ll ans = 0;
    for( ll d = 1; d * d <= n; ++ d ) {
        if( n % d != 0 ) continue;
        ans += phi( d ) * n / d;
        if( d * d != n ) ans += phi( n / d ) * d;
    }
    cout << ans << '\n';
}

int main( ) {
    int T = 1;
    while( T -- ) solve( );
    return 0;
}

Q7 P2398 GCD SUM

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 3e5 + 5;

ll read( ) { /* 模板代码略 */ }

int pri[maxn], pcnt;
bool isp[maxn];
ll phi[maxn];
void sieve( int N ) { /* 模板代码略 */ }

ll pre_phi[maxn];

void init( int N ) {
    sieve( N );
    for( int i = 1; i <= N; ++ i ) {
        pre_phi[i] = pre_phi[i - 1] + phi[i];
    }
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        res += ( pre_phi[r] - pre_phi[l - 1] ) * vn * vm;
    }
    return res;
}

void solve( ) {
    int n = read( );
    cout << calc2( n, n ) << '\n';
}

int main( ) {
    init( maxn - 1 );
    int T = 1;
    while( T -- ) solve( );
    return 0;
}

Q8 P4449 于神之怒加强版

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
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 5e6 + 5;
const int mod = 1e9 + 7;

ll read( ) { /* 模板代码略 */ }

ll qpow( ll a, ll k, ll mod ) { /* 模板代码略 */ }

ll K;
int pri[maxn], pcnt;
bool isp[maxn];
ll J[maxn], pre_J[maxn];

void sieve( int N ) {
    pcnt = 0;
    fill( isp, isp + N + 1, true );
    isp[0] = isp[1] = false;
    J[1] = 1;
    for( int i = 2; i <= N; ++ i ) {
        if( isp[i] ) {
            pri[++ pcnt] = i;
            ll pk = qpow( i, K, mod );
            J[i] = ( pk - 1 + mod ) % mod;
        }
        for( int j = 1; j <= pcnt && 1LL * i * pri[j] <= N; ++ j ) {
            int p = pri[j];
            isp[i * p] = 0;
            if( i % p == 0 ) {
                ll pk = ( J[p] + 1 ) % mod;
                J[i * p] = ( J[i] * pk ) % mod;
                break;
            }
            J[i * p] = ( J[i] * J[p] ) % mod;
        }
    }
    for( int i = 1; i <= N; ++ i ) {
        pre_J[i] = ( pre_J[i - 1] + J[i] ) % mod;
    }
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        ll sum_J = ( pre_J[r] - pre_J[l - 1] + mod ) % mod;
        res = ( res + ( sum_J * vn % mod * vm % mod ) ) % mod;
    }
    return res;
}

void solve( ) {
    int n = read( ), m = read( );
    cout << calc2( n, m ) << '\n';
}

int main( ) {
    int T = read( );
    K = read( );
    sieve( maxn - 1 );
    while( T -- ) solve( );
    return 0;
}

四、带权 GCD 与 LCM 求和

Q9 P1829 Crash 的数字表格 / JZPTAB

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e7 + 5;
const int mod = 20101009;

ll read( ) { /* 模板代码略 */ }

int pri[maxn / 10], pcnt;
bool isp[maxn];
int mu[maxn];
void sieve( int N ) { /* 模板代码略 */ }

const ll inv2 = ( mod + 1 ) / 2;

ll S1( ll n ) {
    n %= mod;
    return n * ( n + 1 ) % mod * inv2 % mod;
}

ll h[maxn], pre_h[maxn];

void init( int N ) {
    sieve( N );
    for( int k = 1; k <= N; ++ k ) {
        if( mu[k] == 0 ) continue;
        ll val = ( 1ll * mu[k] * k % mod + mod ) % mod;
        for( int t = k; t <= N; t += k ) {
            h[t] = ( h[t] + val ) % mod;
        }
    }
    for( int t = 1; t <= N; ++ t ) {
        h[t] = ( h[t] * t ) % mod;
        pre_h[t] = ( pre_h[t - 1] + h[t] ) % mod;
    }
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        ll sum_h = ( pre_h[r] - pre_h[l - 1] + mod ) % mod;
        res = ( res + sum_h * S1( vn ) % mod * S1( vm ) % mod ) % mod;
    }
    return res;
}

void solve( ) {
    int n = read( ), m = read( );
    cout << calc2( n, m ) << '\n';
}

int main( ) {
    init( maxn - 1 );
    int T = 1;
    while( T -- ) solve( );
    return 0;
}

Q10 P3768 简单的数学题

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 5e6 + 5;
ll mod, inv2, inv6;

ll read( ) { /* 模板代码略 */ }

ll qpow( ll a, ll k, ll mod ) { /* 模板代码略 */ }

ll S1( ll n ) {
    n %= mod;
    return n * ( n + 1 ) % mod * inv2 % mod;
}

ll S2( ll n ) {
    n %= mod;
    return n * ( n + 1 ) % mod * ( 2 * n + 1 ) % mod * inv6 % mod;
}

ll S3( ll n ) {
    ll s = S1( n );
    return s * s % mod;
}

unordered_map<ll, ll> mp_h;
int pri[maxn / 10], pcnt;
bool isp[maxn];
ll phi[maxn];
int pre_h[maxn];
ll preN;

void sieve( int N ) {
    preN = N, pcnt = 0;
    mp_h.clear( );
    fill( isp, isp + N + 1, true );
    isp[0] = isp[1] = false;
    phi[1] = 1;
    for( int i = 2; i <= N; ++ i ) {
        if( isp[i] ) pri[++ pcnt] = i, phi[i] = i - 1;
        for( int j = 1; j <= pcnt && 1LL * i * pri[j] <= N; ++ j ) {
            int p = pri[j];
            isp[i * p] = 0;
            if( i % p == 0 ) {
                phi[i * p] = phi[i] * p;
                break;
            }
            phi[i * p] = phi[i] * ( p - 1 );
        }
    }
    for( ll i = 1; i <= N; ++ i ) {
        int hi = i * i % mod * phi[i] % mod;
        pre_h[i] = ( pre_h[i - 1] + hi ) % mod;
    }
}

ll sum_h( ll N ) {
    if( N <= preN ) return pre_h[N];
    if( mp_h.count( N ) ) return mp_h[N];
    ll res = S3( N );
    for( ll l = 2, r; l <= N; l = r + 1 ) {
        ll v = N / l;
        r = N / v;
        ll sum_d2 = ( S2( r ) - S2( l - 1 ) + mod ) % mod;
        res = ( res - sum_d2 * sum_h( v ) % mod + mod ) % mod;
    }
    return mp_h[N] = res;
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        ll sum = ( sum_h( r ) - sum_h( l - 1 ) + mod ) % mod;
        res = ( res + sum * S1( vn ) % mod * S1( vm ) % mod ) % mod;
    }
    return res;
}

void solve( ) {
    mod = read( );
    ll n = read( );
    sieve( maxn - 1 );
    inv2 = qpow( 2, mod - 2, mod );
    inv6 = qpow( 6, mod - 2, mod );
    cout << calc2( n, n ) << '\n';
}

int main( ) {
    int T = 1;
    while( T -- ) solve( );
    return 0;
}

五、非 F(gcd⁡)F(\gcd) 型卷积分离

Q11 P3327 约数个数和

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 3e5 + 5;

ll read( ) { /* 模板代码略 */ }

int pri[maxn], pcnt;
bool isp[maxn];
int mu[maxn];
void sieve( int N ) { /* 模板代码略 */ }

ll pre_mu[maxn];
ll D[maxn];
ll pre_D[maxn];

void init( int N ) {
    sieve( N );
    for( int d = 1; d <= N; ++ d ) {
        for( int x = d; x <= N; x += d ) {
            D[x] ++;
        }
    }
    for( int i = 1; i <= N; ++ i ) {
        pre_mu[i] = pre_mu[i - 1] + mu[i];
        pre_D[i] = pre_D[i - 1] + D[i];
    }
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        ll sum_mu = pre_mu[r] - pre_mu[l - 1];
        res += sum_mu * pre_D[vn] * pre_D[vm];
    }
    return res;
}

void solve( ) {
    int n = read( ), m = read( );
    cout << calc2( n, m ) << '\n';
}

int main( ) {
    init( maxn - 1 );
    int T = read( );
    while( T -- ) solve( );
    return 0;
}

六、进阶变化

Q12 P3312 数表

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5 + 5;
const ll mod = ( 1ll << 31 );

ll read( ) { /* 模板代码略 */ }

struct BIT {
/* ================================================== */
ll tr[maxn];
int sz;
void init( int N ) { sz = N;
    fill( tr, tr + sz + 1, 0 );
}
void add( int idx, ll val ) {
    val %= mod;
    for( int i = idx; i <= sz; i += i & -i ) {
        tr[i] += val;
        if( tr[i] >= mod ) tr[i] -= mod;
    }
}
ll ask( int idx ) {
    ll res = 0;
    for( int i = idx; i; i -= i & -i ) {
        res += tr[i];
        if( res >= mod ) res -= mod;
    }
    return res;
}
/* ================================================== */
} bit;

int pri[maxn], pcnt;
bool isp[maxn];
int mu[maxn], sigma[maxn];

void sieve( int N ) { /* 模板代码略 */ }

void init( int N ) {
    sieve( N );
    for( int d = 1; d <= N; ++ d ) {
        for( int x = d; x <= N; x += d ) {
            sigma[x] += d;
        }
    }
}

struct Query { int n, m, a, id; };

ll calc2( int n, int m ) {
    if( n > m ) swap( n, m );
    ll res = 0, pre = 0;
    for( int l = 1, r; l <= n; l = r + 1 ) {
        int vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        ll cur = bit.ask( r );
        ll sum_G = ( cur - pre + mod ) % mod;
        pre = cur;
        ll cnt = 1ll * vn * vm % mod;
        res = ( res + sum_G * cnt ) % mod;
    }
    return res;
}

void solve( ) {
    int Q = read( );
    vector<Query> qs( Q );
    int N = 0;

    for( int i = 0; i < Q; ++ i ) {
        int n = read( ), m = read( ), a = read( );
        if( n > m ) swap( n, m );
        qs[i] = { n, m, a, i };
        N = max( N, n );
    }

    init( N );
    bit.init( N );

    vector<int> ds( N );
    iota( ds.begin( ), ds.end( ), 1 );
    sort( ds.begin( ), ds.end( ), [&]( int x, int y ) {
        return sigma[x] < sigma[y];
    } );

    sort( qs.begin( ), qs.end( ), []( const Query &x, const Query &y ) {
        return x.a < y.a;
    } );

    vector<ll> ans( Q );
    int ptr = 0;

    for( auto [n, m, a, idx] : qs ) {
        while( ptr < N && sigma[ds[ptr]] <= a ) {
            int d = ds[ptr ++];
            for( int k = 1; 1ll * d * k <= N; ++ k ) {
                if( mu[k] == 0 ) continue;
                bit.add( d * k, 1ll * sigma[d] * mu[k] );
            }
        }
        ans[idx] = calc2( n, m );
    }

    for( ll x : ans ) cout << x << '\n';
}

int main( ) {
    int T = 1;
    while( T -- ) solve( );
    return 0;
}

Q13 P3704 数字表格

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

ll read( ) { /* 模板代码略 */ }

ll mul( ll a, ll b, ll mod ) { /* 模板代码略 */ }

ll qpow( ll a, ll k, ll mod ) { /* 模板代码略 */ }

ll inv( ll a, ll mod ) { /* 模板代码略 */ }

int pri[maxn], pcnt;
bool isp[maxn];
ll phi[maxn];
int mu[maxn];
void sieve( int N ) { /* 模板代码略 */ }

ll F[maxn], preF[maxn], ipreF[maxn];
ll G[maxn], preG[maxn], ipreG[maxn];

void init( int N ) {
    sieve( N );
    F[0] = 0, F[1] = 1;
    preF[0] = 1, preF[1] = 1;
    for( ll i = 2; i <= N; ++ i ) {
        F[i] = ( F[i - 1] + F[i - 2] ) % mod;
        preF[i] = ( preF[i - 1] * F[i] ) % mod;
    }
    ipreF[N] = inv( preF[N], mod );
    for( int i = N - 1; i >= 0; -- i ) {
        ipreF[i] = mul( ipreF[i + 1], F[i + 1], mod );
    }

    for( int i = 1; i <= N; ++ i ) G[i] = 1;
    
    for( int d = 1; d <= N; ++ d ) {
        ll invF = mul( ipreF[d], preF[d - 1], mod );
        for( int T = d; T <= N; T += d ) {
            if( mu[T / d] == 1 ) G[T] = mul( G[T], F[d], mod );
            else if( mu[T / d] == -1 ) G[T] = mul( G[T], invF, mod );
        }
    }

    preG[0] = 1;
    for( int i = 1; i <= N; ++ i ) {
        preG[i] = mul( preG[i - 1], G[i], mod );
    }
    ipreG[N] = inv( preG[N], mod );
    for( int i = N - 1; i >= 0; -- i ) {
        ipreG[i] = mul( ipreG[i + 1], G[i + 1], mod );
    }
}

ll calc2( ll n, ll m, ll k = 1 ) {
    if( n > m ) swap( n, m );
    n /= k, m /= k;
    ll res = 1;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );
        ll a = mul( preG[r], ipreG[l - 1], mod );
        ll e = ( vn * vm ) % ( mod - 1 );
        res = mul( res, qpow( a, e, mod ), mod );
    }
    return ( res + mod ) % mod;
}

void solve( ) {
    int n = read( ), m = read( );
    cout << calc2( n, m ) << '\n';
}

int main( ) {
    init( maxn - 1 );
    int T = read( );
    while( T -- ) solve( );
    return 0;
}
旧算法 > 数学
#数学/数论 #数学/算术函数
数论求和题型整理_代码
http://miqiu.space/posts/4b5471b2/
作者
Miqiu
发布于
2026年8月10日
许可协议