DDOSvoid's Blog

Luogu P5655 基础数论函数练习题

发表于 更新于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P5655

简要题意：有 $T$ 组数据，给定一个长度为 $n$ 的序列 $a_i$，$m$ 次询问 $[a_l,a_{l+1},\cdots,a_r]$，答案对 $10^9+7$​ 取模

$n,m,T\le 300,a_i\le 2^{60}$

Solution

首先我们考虑使用求多个数的 $lcm$ 的通用解法，我们逐步计算 $lcm$，每次合并

但是现在的问题是之前所有数的 $lcm$ 太大，不能用 $ll$ 存下，所以我们考虑 $lcm$ 另外存取

我们令 $[a_1,a_2,\cdots,a_{n-1}]=\prod_{i=1}^{n-1}b_i$，那么我们现在只需要求 $([a_1,a_2,\cdots,a_{n-1}],a_n)$​

这个东西就是 $(\prod_{i=1}^{n-1}b_i,a_n)$，这个东西显然可以在乘的时候对 $a_n$ 取模

那么 $b_n$ 就等于 $\frac{a_n}{(\prod_{i=1}^{n-1}b_i,a_n)}$，实际上就是把多余的给除掉

这样我们就得到了一个 $O(Tn^3)$ 的算法

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
#include <iostream>
#include <cstdio>
#define maxn 310
#define ll long long
using namespace std;

const int p = 1000000007;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

ll mul(ll x, ll y, ll p) {
    return (x * y - (ll) ((long double) x / p * y) * p + p) % p;
}

int n, m;

ll a[maxn], b[maxn];

void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    while (m--) {
        int l, r; cin >> l >> r;
        ll ans = 1; 
        for (int i = l; i <= r; ++i) {
            ll s = 1; b[i] = a[i]; 
            for (int j = l; j < i; ++j) s = mul(s, b[j], a[i]); 
            b[i] /= gcd(b[i], s); 
            ans = ans * (b[i] % p) % p; 
        }
        cout << ans << "\n"; 
    } 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}

为了进一步优化复杂度，我们考虑分治

在分治中我们可以 $O(n^2)$ 预处理，然后再合并

总的时间复杂度为 $O(Tn^2\log n)$​ 实际上依然不能通过此题

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 <iostream>
#include <cstdio>
#define maxn 310
#define ll long long
#define ldb long double
using namespace std;

const int p = 1000000007;

ll mul(ll x, ll y, ll p) {
    return (x * y - (ll)((ldb) x / p * y) * p + p) % p;
}

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } 

int n, m;

ll a[maxn], ans[maxn][maxn];

ll b[maxn]; 
void solve(int l, int r) {
    if (l == r) return ans[l][l] = a[l] % p, void();
    int m = l + r >> 1;
    solve(l, m); solve(m + 1, r); 
    for (int i = m; i >= l; --i) {
        ll s = 1; b[i] = a[i];
        for (int j = m; j > i; --j) s = mul(s, b[j], b[i]);
        b[i] /= gcd(b[i], s); 
    }
    for (int i = m + 1; i <= r; ++i) {
        ll s = 1; b[i] = a[i];
        for (int j = m + 1; j < i; ++j) s = mul(s, b[j], b[i]);
        b[i] /= gcd(b[i], s); 
    }
    ll s1 = 1, s2;
    for (int i = m; i >= l; --i) {
        s1 = s1 * (b[i] % p) % p; s2 = s1;
        for (int j = m + 1; j <= r; ++j) {
            ll s = gcd(b[i], b[j]);
            b[i] /= s; b[j] /= s;
            ans[i][j] = s2 = s2 * (b[j] % p) % p; 
        } 
    } 
} 

void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    solve(1, n); 
    while (m--) {
        int l, r; cin >> l >> r;
        cout << ans[l][r] << "\n";
    } 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}

所以我们还有另一种 $O(Tn(n+\log ^2v))$ 的做法，留坑