for (int i = 1; i <= n; i++) { a[i] = read(); for (auto x : fac[a[i]]) { pos[x].eb(i); } }
vector<vector<pii>> qry(n + 1); for (int i = 1; i <= m; i++) { int l = read(), r = read(); if (r - l <= 1) continue; qry[r].eb(l, i); }
DS::init(n);
vector<vector<pii>> cand(n + 1); for (int d = 1; d <= M; d++) { vector<int> b; for (int i : pos[d]) b.eb(i); for (int i = 0; i + 1 < b.size(); i++) { int need = b[i + 1] * 2 - b[i]; auto it = ranges::lower_bound(b, need); if (it == b.end()) continue; cand[*it].eb(b[i], d); } }
vector<int> ans(n + 1); for (int r = 1; r <= n; r++) { for (auto [l, d] : cand[r]) { DS::update(l, d); } for (auto [l, id] : qry[r]) { ans[id] = DS::query(l); } }
for (int i = 1; i <= m; i++) { cout << ans[i] << '\n'; } }
signedmain(){ for (int i = 1; i <= M; i++) { for (int j = i; j <= M; j += i) { fac[j].eb(i); } } solve(); return0; }
F - An Easy Counting Problem
给定三个数 $k, p, x$:
$p$ 是质数;
$k$ 以二进制字符串形式输入,实际表示一个很大的整数;
我们要统计满足
$$ 0 \le b \le a < p^k,\quad \binom{a}{b} \equiv x \pmod p $$
的整数对 $(a,b)$ 的数量,并对答案取模 $998244353$。
首先,根据 Lucas 定理,拆成 $k$ 个位上的乘积
当 $p$ 是质数时:
$$ \binom{a}{b} \equiv \prod_{i=0}^{k-1} \binom{a_i}{b_i} \pmod p $$
intfindPrimitiveRoot(int p){ int rt = 1; while (1) { bool ok = 1; int v = 1; for (int i = 1; i < p - 1; i++) { v = v * rt % p; if (v == 1) { ok = false; } } if (ok) { break; } rt++; } return rt; }
voidsolve(){ string k; cin >> k; int p = read(), x = read(); int rt = findPrimitiveRoot(p); vector<int> lg(p); for (int i = 0, v = 1; i < p - 1; i++) { lg[v] = i; v = v * rt % p; } vector g(p, vector(p, 0ll)); Poly<P> f(p - 1); for (int i = 0; i < p; i++) { g[i][0] = 1; for (int j = 1; j <= i; j++) { g[i][j] = g[i - 1][j] + g[i - 1][j - 1]; if (g[i][j] >= p) { g[i][j] -= p; } } for (int j = 0; j <= i; j++) { f[lg[g[i][j]]] += 1; } } Poly<P> ans(p - 1); ans[0] = 1; for (int i = k.size() - 1; i >= 0; i--) { if (k[i] == '1') { ans *= f; for (int j = p - 1; j < ans.size(); j++) { ans[j - (p - 1)] += ans[j]; } ans.resize(p - 1); } f *= f; for (int j = p - 1; j < f.size(); j++) { f[j - (p - 1)] += f[j]; } f.resize(p - 1); } cout << ans[lg[x]] << "\n"; }
vector<int> deg(n + 1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (g[i][j]) deg[i]++; } }
int A = 1, B = -1, C = -1; for (int i = 2; i <= n; i++) { if (deg[i] > deg[A]) A = i; }
if (deg[A] == n - 1) { cout << "NOT FOUND\n"; return; }
vector<int> s1(n + 1); for (int i = 1; i <= n; i++) { if (g[i][A]) s1[i] = 1, B = i; } if (B == -1) { cout << "NOT FOUND\n"; return; } deg.assign(n + 1, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (s1[i] and s1[j] and g[i][j]) { deg[i]++; } } } for (int i = 2; i <= n; i++) { if (s1[i] and deg[i] > deg[B]) B = i; }
vector<int> s2(n + 1); for (int i = 1; i <= n; i++) { if (g[i][B]) s2[i] = 1, C = i; } if (C == -1) { cout << "NOT FOUND\n"; return; } deg.assign(n + 1, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (s2[i] and s2[j] and g[i][j]) { deg[i]++; } } } for (int i = 2; i <= n; i++) { if (s2[i] and deg[i] > deg[C]) C = i; }
#define ls (p << 1) #define rs (p << 1 | 1) #define mid (l + r >> 1)
voidsolve(){ int n = read(); int k = read(); int all = 1 << n; vector<int> a(all + 1); for (int i = 1; i <= all; i++) a[i] = read(); vector<int> pos(all + 1); for (int i = 1; i <= all; i++) pos[a[i]] = i;
vector<int> sum(all << 2), ans(all + 1);
for (int i = 1; i <= all; i++) { int x = pos[i]; vector<int> v;
auto get = [&](thisauto&& get, int p, int l, int r) -> void { ++sum[p]; v.eb(sum[p]);
int res = n; for (int j = 0; j < v.size(); j++) { int t = 1 << j; if (t <= i and t - v[j] <= k) continue; res = j - 1; break; } ans[x] = res; } for (int i = 1; i <= all; i++) { cout << ans[i] << " \n"[i == all]; } }
std::vector<int> minp, primes; voidsieve(int n){ minp.assign(n + 1, 0), primes.clear(); for (int i = 2; i <= n; i++) { if (minp[i] == 0) minp[i] = i, primes.push_back(i); for (auto p : primes) { if (i * p > n) break; minp[i * p] = p; if (p == minp[i]) break; } } }
voidsolve(){ int n = read();
int ans = 1; for (auto p : primes) { int cnt = 0; while (n % p == 0) n /= p, cnt++; if (cnt != 0) ans *= (2 * cnt + 1); }
if (n > 1) ans *= 3; ans = (ans + 1) / 2; cout << ans << '\n'; }
signedmain(){ sieve(1e6); for (int T = read(); T--; solve()); return0; }
node get(string s){ s = s.substr(s.find("for ") + 4);
auto i = s.substr(0, s.find(' '));
s = s.substr(s.find('('));
auto a = s.substr(1, s.find(',') - 1);
s = s.substr(s.find(',') + 1); // cout << "--" << s << '\n';
string b, c; if (s.find(',') != string::npos) { b = s.substr(0, s.find(',')); s = s.substr(s.find(',') + 1); c = s.substr(0, s.find(')')); } else { b = s.substr(0, s.find(')')); c = "1"; }
return node {i, a, b, c}; }
voidsolve(){ string s; getline(cin, s); getline(cin, s); auto [i, a, b, c] = get(s); getline(cin, s); auto [j, d, e, f] = get(s);
// cout << i << ' ' << a << ' ' << b << ' ' << c << '\n'; // cout << j << ' ' << d << ' ' << e << ' ' << f << '\n';
// getline(cin, s);
// s = s.substr(7); // cout << s << '\n';
int ans = 0; int va = stoi(a); int vb = stoi(b); int vc = stoi(c);
for (int i = va; (vc > 0 ? i < vb : i > vb); i += vc) { int vd = isalpha(d[0]) ? i : stoi(d); int ve = isalpha(e[0]) ? i : stoi(e); int vf = isalpha(f[0]) ? i : stoi(f); if (vf > 0) { if (vd < ve) { int k = (ve - vd - 1) / vf; ans += (vd + vd + k * vf) * (k + 1) / 2; } } else { if (vd > ve) { int k = (vd - ve - 1) / -vf; ans += (vd + vd + k * vf) * (k + 1) / 2; } } }