https://codeforces.com/contest/1654

D. Potion Brewing Class

 

题意：有长为 nn 的正整数数组 aa，给定 n−1n-1 个条件，每个条件要求 ai/aj=x/ya_i/a_j=x/y，问数组所有元素的和，mod 998244353。

dfs

nn 个点，n−1n-1 个条件，刚好建成一棵树，每条边为儿子与父亲的比值，根为 a1a_1，则 ai=a1a_i=a_1乘 ii 到根的路径上边权的的积。aia_i 是正整数说明 a1a_1 是所有分母的lcm。求出 a1a_1 后再遍历求和即可。

但是要取模，无法求lcm。所以质因数分解，记录每个质数的最大出现次数，乘起来就是lcm。

分子要用来约分，所以同样要一路记下来。

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;
typedef pair<int, int> pii;

ll inv[N];
void init() {
    inv[0] = inv[1] = 1;
    for (ll i = 2; i < N; i++)
        inv[i] = (mod - mod / i)*inv[mod%i] % mod;
}

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

ll prime[N];     //记录质数
bool is_prime[N];
ll vis[N];      //记录最小质因子
int euler_sieve(int n) {
    int cnt = 0;
    memset(vis, 0, sizeof(vis));
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = i;
            prime[cnt++] = i;
            is_prime[i] = true;
        }    //vis[]记录x的最小质因子
        for (int j = 0; j < cnt; j++) {
            if (i * prime[j] > n) break;
            vis[i * prime[j]] = prime[j];              //vis[]记录x的最小质因子
            if (i % prime[j] == 0)
                break;
        }
    }
    return cnt;
}

int mxc[N], cnt[N], fcnt[N];

int T;
int n;
vector<int> G[N];
ll up[N], dn[N], fa[N];
ll ans;
struct X {
    int u, v, x, y;
};
vector<X> vc;

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

void dfs(int u, int _fa) {
    fa[u] = _fa;
    for (int v: G[u]) {
        if (v == _fa)continue;
        dfs(v, u);
    }
}

vector<pii> st[N], fst[N];
void dfs2(int u, int _fa) {
    for (int v: G[u]) {
        if (v == _fa)continue;
        ll x = up[v];
        st[v].clear();
        fst[v].clear();
        for (int i = 0; prime[i] * prime[i] <= x && x > 1; i++) {
            if (x % prime[i] == 0)fst[v].push_back({prime[i], fcnt[prime[i]]});
            while (x % prime[i] == 0) {
                x /= prime[i];
                fcnt[prime[i]]++;
            }
        }
        if (x != 1){
            fst[v].push_back({x, fcnt[x]});
            fcnt[x]++;
        }
        x = dn[v];
        for (int i = 0; prime[i] * prime[i] <= x && x > 1; i++) {
            if (x % prime[i] == 0)st[v].push_back({prime[i], cnt[prime[i]]});
            while (x % prime[i] == 0) {
                x /= prime[i];
                cnt[prime[i]]++;
                mxc[prime[i]] = max(mxc[prime[i]], cnt[prime[i]] - fcnt[prime[i]]);
            }
        }
        if (x != 1){
            st[v].push_back({x, cnt[x]});
            cnt[x]++, mxc[x] = max(mxc[x], cnt[x] - fcnt[x]);
        }

        dfs2(v, u);

        while (!st[v].empty()) {
            pii p = st[v].back();
            st[v].pop_back();
            cnt[p.first] = p.second;
        }
        while (!fst[v].empty()) {
            pii p = fst[v].back();
            fst[v].pop_back();
            fcnt[p.first] = p.second;
        }
    }
}

void dfs3(int u, int _fa, ll tmp){
    ll ttmp = tmp;
    for(int v:G[u]){
        if(v == _fa)continue;
        tmp = ttmp;
        ll x = up[v];
        for (int j = 0; prime[j] * prime[j] <= x && x > 1; j++) {
            while (x % prime[j] == 0) {
                x /= prime[j];
                tmp = tmp * prime[j] % mod;
            }
        }
        if(x != 1)tmp = tmp * x % mod;
        x = dn[v];
        for (int j = 0; prime[j] * prime[j] <= x && x > 1; j++) {
            while (x % prime[j] == 0) {
                x /= prime[j];
                tmp = tmp * inv[prime[j]] % mod;
            }
        }
        if(x != 1)tmp = tmp * inv[x] % mod;
        ans = (ans + tmp) % mod;
        dfs3(v, u, tmp);
    }
}

int main() {
    init();
    euler_sieve(200000);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        fill(mxc, mxc + n + 1, 0);
        fill(cnt, cnt + n + 1, 0);
        fill(fcnt, fcnt + n + 1, 0);
        for (int i = 1; i <= n; i++)G[i].clear();
        vc.clear();
        for (int i = 1; i < n; i++) {
            int u, v, x, y;
            scanf("%d%d%d%d", &u, &v, &x, &y);
            int g = gcd(x, y);
            vc.push_back({u, v, x / g, y / g});
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1, 0);
        for (auto e: vc) {
            if (fa[e.u] == e.v)up[e.u] = e.x, dn[e.u] = e.y;
            else up[e.v] = e.y, dn[e.v] = e.x;
        }
        up[1] = dn[1] = 1;
        dfs2(1, 0);
        ll lcm = 1;
        for(int i = 2; i <= n; i++){
            if(mxc[i] > 0)lcm = lcm * Pow(i, mxc[i]) % mod;
        }
        ans = lcm;
        dfs3(1, 0, lcm);
        printf("%lld\n", ans);
    }
    return 0;
}

 

E. Arithmetic Operations

 

题意：给一个定长为 n≤105n\le 10^5 的数列 a,1≤ai≤105a,1\le a_i\le 10^5，可以进行任意次操作，每次操作选任意一个位置 ii，把 aia_i 变成任意数，问最少操作次数使 aa 为等差数列。

根号分块，枚举

复杂度 O(nn)\mathcal{O}(n\sqrt{n}).

暴力做法是枚举公差，遍历数列求每个元素在该公差时对应的初值。复杂度 O(n2)\mathcal{O}(n^2)。

  • 枚举 ∣d∣∈[0,105]|d|\in [0,\sqrt{10^5}] 的公差 dd，暴力求解。

  • 对于 ∣d∣>105|d|>\sqrt{10^5} 的公差 dd，遍历数列，若保留该元素不变，则该元素周围最多 105∣d∣=O(n)\frac{10^5}{|d|}= \mathcal{O}(\sqrt{n}) 中每个元素在最终的等差数列中小于等于 10510^5，其他元素必定大于 10510^5，也就必定要被改变。

    但是直接枚举还是不行。不能枚举公差。直接遍历数列，假设当前元素保持不变，枚举该元素周围 105\sqrt{10^5} 个元素，作为另一个保持不变的数，计算出公差，统计相同的公差个数。

    这样枚举的解集是枚举公差 ∣d∣>105|d|>\sqrt{10^5} 时的超集。

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
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 1e8 + 10;
typedef pair<int, int> pii;

int n;
int a[200010], cnt[N];
const int base = 4e7, blk = 320;

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
    int mx = 0;
    for(int d = -blk; d <= blk; d++){
        for(int i = 1; i <= n; i++){
            mx = max(mx, ++cnt[a[i] - (i - 1) * d + base]);
        }
        for(int i = 1; i <= n; i++){
            cnt[a[i] - (i - 1) * d + base]--;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= min(n, i + blk); j++){
            if((a[j] - a[i]) % (j - i) != 0)continue;
            cnt[((a[j] - a[i]) / (j - i)) + base]++;
            mx = max(mx, 1 + cnt[((a[j] - a[i]) / (j - i)) + base]);
        }
        for(int j = i + 1; j <= min(n, i + blk); j++){
            if((a[j] - a[i]) % (j - i) != 0)continue;
            cnt[((a[j] - a[i]) / (j - i)) + base]--;
        }
    }
    printf("%d\n", n - mx);
    return 0;
}