P8193 [USACO22FEB] 高维前缀和

题意

传送门 P8193 [USACO22FEB] Sleeping in Class P

题解

令 $s=\sum a_i$，$presu{m}_i={\sum }_{j\le i}{a}_j$。对于第 $i$ 个询问，存在满足条件操作的充要条件是 $q_i|s$。令 $x=\sum [presu{m}_i\mathrm{mod}{q}_i=0]$。 至少需要合并的次数为 $n-x$，至少需要分裂的次数为 $s/q_i-x$，且这样的操作可以满足条件。答案为 $n+s/q_i-2x$。

$q_i$ 是 $s$ 的因数，则对有所有前缀和，只需考虑它们与 $s$ 的公因子。将所有数字按照算数基本定理进行分解，则问题转化为求 $q_i$ 对应的高维前缀和。高维前缀和可参考 Some SOS DP Insights。

大数分解可以使用 Pollard-Rho 算法。另一种做法是只筛 $[1,10^6]$ 的质因子，若最后得到的数 $n\le 10^{12}$ ，由于合数存在小于等于 $\sqrt{n}$ 的因子，故 $n$ 是质数，质因数分解完毕，直接算高维前缀和即可。若 $n>10^{12}$，则存在两个大于 $10^{12}$ 的质数，则总的质因子数上界为 $ma{x}_{1\le i\le 10^6}d(i)\times 2^2$，其中 $d(i)$ 代表 $i$ 的因数数量，实际上数量较小，可以直接暴力算 $x$，记忆化优化即可。

#include 
using namespace std;
using ll = long long;

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

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

    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i + 1 < n; ++i) {
        a[i + 1] += a[i];
    }
    ll s = a[n - 1];

    for (int i = 0; i < n; ++i) {
        a[i] = gcd(a[i], s);
    }

    map<ll, int> prime;
    bool bf = 0;
    {
        ll x = s;
        for (int i = 2; i <= 1e6; ++i) {
            while (x % i == 0) {
                prime[i] += 1;
                x /= i;
            }
        }

        if (x > 1) {
            if (x > 1e12) {
                bf = 1;
            } else {
                prime[x] += 1;
            }
        }
    }

    vector<int> dim;
    for (auto [x, c] : prime) {
        dim.push_back(c + 1);
    }
    int m = dim.size();
    vector<int> bs(m + 1);
    bs[0] = 1;
    for (int i = 0; i < m; ++i) {
        bs[i + 1] = bs[i] * dim[i];
    }

    auto get = [&](ll x) {
        vector<int> c;
        for (auto [p, _] : prime) {
            int t = 0;
            while (x % p == 0) {
                ++t;
                x /= p;
            }
            c.push_back(t);
        }

        int res = 0;
        for (int i = 0; i < m; ++i) {
            res += c[i] * bs[i];
        }
        return res;
    };

    vector<int> sum(bs[m]);
    for (auto x : a) {
        sum[get(x)] += 1;
    }
    for (int i = 0; i < m; ++i) {
        for (int j = bs[m] - 1; j >= 0; --j) {
            if (j / bs[i] % dim[i] == dim[i] - 1) continue;
            sum[j] += sum[j + bs[i]];
        }
    }

    int q;
    cin >> q;
    map<ll,ll> mem;
    while (q--) {
        ll b;
        cin >> b;
        if (s % b > 0) {
            cout << "-1\n";
            continue;
        }
        if (bf) {
            if (mem.count(b) == 0) {
                int x = 0;
                for (int i = 0; i < n; ++i) {
                    x += a[i] % b == 0;
                }
                mem[b] = s / b + n - 2 * x;
            }
            cout << mem[b] << '\n';
        } else {
            ll res = s / b + n - sum[get(b)] * 2;
            cout << res << '\n';
        }
    }

    return 0;
}
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