CWOI2020 数论提高 题解

难难

POJ 3253 Round Numbers

求在 [l, r] 中，满足二进制下 0 的位数比 1 的位数多的数的个数。

l, r \leq 2 * 10^9

等价于求 [1, x) 中满足题意的数。

分为二进制位数比 x 小的与等于 x 的处理。

小的枚举 1 的数量，多的枚举从哪一位开始不同并枚举 1 的数量。

时间复杂度 O(\log^2n)

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 30 + 10;

int n, m, binom[MAXN][MAXN];

int round(int x) {
    int bit[MAXN];
    memset(bit, 0, sizeof bit);
    int ret = 0, sz = 0, tmp = x;
    while (tmp) {
        bit[++sz] = (tmp & 1);
        tmp >>= 1;
    }
    for (int i = 2; i < sz; ++i) for (int j = (i + 1) >> 1; j <= i - 1; ++j) ret += binom[i - 1][j];
    int zr = 0;
    int cnt = (sz + 1) >> 1;
    for (int i = sz - 1; i >= 1; --i) {
        if (!bit[i]) zr++;
        else {
            int nzr = zr + 1;
            for (int j = cnt - nzr; j <= i - 1; ++j) ret += binom[i - 1][j];
        }
    }
    return ret;
}

int main() {
    int l, r;
    scanf("%d %d", &l, &r);
    for (int i = 0; i < MAXN; ++i) {
        binom[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
        }
    }
    printf("%d\n", round(r + 1) - round(l));
    return 0;
}

HDU 5288 OO’s Sequence

给出序列 a

令 f(l, r) 表示，在 [l, r] 中 i 的个数，i 满足区间中其他任意数都不是 a_i 因数

求 \sum_{l = 1}^n \sum_{r = 1}^n f(l, r)

|a| \leq 10000

考虑每个数的贡献。

处理出 l_i, r_i，表示在 [1, i) 中，最靠右的 a_i 的因数与 (i, n] 中最靠左的 a_i 的因数。

则每个数的贡献为 (i - l_i + 1) * (r_i - i + 1)。

利用链表或类似思想即可。

时间复杂度 O(d(n)n)

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 10, P = 1e9 + 7;

int n, a[MAXN], pre[MAXN], lft[MAXN], rgt[MAXN];
vector<int> fac[MAXN];
ll ans;

void solve() {
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    memset(pre, 0, sizeof pre);
    for (int i = 1; i <= n; ++i) {
        int pre_pos = 0;
        for (int idx = 0; idx < fac[a[i]].size(); ++idx) { int _fac = fac[a[i]][idx];
            if (pre[_fac]) pre_pos = max(pre_pos, pre[_fac]);
        }
        lft[i] = pre_pos;
        pre[a[i]] = i;
    }
    memset(pre, 0, sizeof pre);
    for (int i = n; i >= 1; --i) {
        int pre_pos = n + 1;
        for (int idx = 0; idx < fac[a[i]].size(); ++idx) { int _fac = fac[a[i]][idx];
            if (pre[_fac]) pre_pos = min(pre_pos, pre[_fac]);
        }
        rgt[i] = pre_pos;
        pre[a[i]] = i;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) (ans += 1ll * (i - lft[i]) * (rgt[i] - i) % P) %= P;
    printf("%d\n", ans);
}

int main() {
    for (int i = 1; i <= 10000; ++i) {
        for (int j = 1; j * j <= i; ++j) if (i % j == 0) fac[i].push_back(j), fac[i].push_back(i / j);
    }
    while (scanf("%d", &n) != EOF) {
        solve();
    }
    return 0;
}

POJ 2142 The Balence

给出 a, b, d，求方程

的一组解，满足 a + b 最小

不妨设 a > b。

exgcd 得出通解 x = x_0 + \dfrac{b}{g}t, y = y_0 - \dfrac{a}{g}t，其中 g = \gcd(a, b)，t \in \mathbb{N}。

由于 a > b，故 \dfrac{a}{g} > \dfrac{b}{g}。

即 y 的斜率更大，那我们优先使 y 最小，即最优解的 t 一定会使 y_0 - \dfrac{a}{g}t 在 0 附近。

时间复杂度 O(\log n)。

#include <cstdio>
#include <algorithm>
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll _abs(ll x) { return x < 0 ? -x : x; }
pll exgcd(ll a, ll b) {
    if (b == 0) return mp(1, 0);
    pll tmp = exgcd(b, a % b);
    pll res = mp(tmp.second, tmp.first - a / b * tmp.second);
    return res;
}
ll a, b, c;

void solve() {
    bool flg = false;
    if (a < b) swap(a, b), flg = true;
    ll g = gcd(a, b);
    if (c % g) { puts("no solution"); return ; }
    pll sol = exgcd(a, b);
    ll x = sol.first, y = sol.second;
    x *= c / g, y *= c / g;
    ll t = y * g / a;
    ll ansx = 0x7fffffff, ansy = 0x7fffffff;
    for (ll i = t - 10; i <= t + 10; ++i) {
        if (_abs(x + b / g * i) + _abs(y - a / g * i) < ansx + ansy) {
            ansx = _abs(x + b / g * i), ansy = _abs(y - a / g * i);
        }
    }
    if (flg) printf("%lld %lld\n", ansy, ansx);
    else printf("%lld %lld\n", ansx, ansy);
}

int main() {
    while (scanf("%lld %lld %lld", &a, &b, &c) && (a && b && c)) solve();
    return 0;
}

一个重要的思想。

SGU 141 Jumping Joe

给出 a, b, P, k，求解关于 x_1, x_2, y_1, y_2 的方程

首先求出通解，使得 x + y 最小，再根据奇偶性判断解的情况即可。

时间复杂度 O(\log n)。

#include <bits/stdc++.h>
#define mkpir make_pair
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll a, b, k, p;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
pll exgcd(ll a, ll b) {
    if (b == 0) return mkpir(1, 0);
    pll tmp = exgcd(b, a % b);
    return mkpir(tmp.second, tmp.first - a / b * tmp.second);
}

int pd(ll x) { return x & 1; }

int main() {
    scanf("%lld %lld %lld %lld", &a, &b, &p, &k);
    bool flg = false;
    if (a < b) swap(a, b), flg = true;
    ll g = gcd(a, b);
    if (p % g) { puts("NO"); return 0; }
    pll sol = exgcd(a, b);
    ll x = sol.first * p / g, y = sol.second * p / g;
    ll t = y * g / a;
    for (ll i = t - 50; i <= t + 50; ++i) {
        ll nx = x + b / g * i, ny = y - a / g * i;
        if (abs(nx) + abs(ny) > k) continue;
        if (!pd(nx + ny - k)) {
            ll ans1, ans2, ans3, ans4;
            ll del = k - abs(nx) - abs(ny);
            if (nx < 0) {
                nx = -nx;
                ans2 = nx + del / 2, ans1 = del / 2;
            } else ans1 = nx + del / 2, ans2 = del / 2;
            if (ny < 0) {
                ny = -ny;
                ans4 = ny, ans3 = 0;
            } else {
                ans3 = ny, ans4 = 0;
            }
            puts("YES");
            return flg ? printf("%lld %lld %lld %lld\n", ans3, ans4, ans1, ans2) & 0 : printf("%lld %lld %lld %lld\n", ans1, ans2, ans3, ans4) & 0;
        }
    }
    puts("NO");
    return 0;
}

F Joseph's Problem

求 \sum_{i = 1}^n k \bmod i

利用数论分块：

\big\lfloor \dfrac{k}{i} \big\rfloor 的值是呈块状的，若某块左端点是 i，则值为 \big\lfloor \dfrac{k}{i} \big\rfloor，右端点是 \big\lfloor k * \big\lfloor \dfrac{k}{i} \big\rfloor^{-1} \big\rfloor。

则可以 O(\sqrt n) 计算。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

ll n, k, ans;

int main() {
    scanf("%lld %lld", &n, &k);
    for (ll l = 1; l <= min(n, k); ) {
        ll r = k / (k / l);
        r = min(n, r);
        ll val = k / l;
        ans += (r - l + 1) * k - val * (l + r) * (r - l + 1) / 2;
        l = r + 1;
    }
    if (n > k) ans += k * (n - k);
    printf("%lld\n", ans);
    return 0;
}

HDU 3398 String

用 n 个 1 与 m 个 0 构造长度为 n + m 的字符，满足任意前缀 1 的个数要大于等于 0。求方案数。

n, m \leq 1000000

考虑坐标轴：填一个 1 就向右走一格，填 2 向上走一格。

则题目为从 (0, 0) 走到 (n, m)，且不经过 y = x + 1 这条线段。

易知总方案数为 \binom{n + m}{n}，则考虑计算不合法方案：

对于一个不合法方案，将 [0, p] 这段区间内的路径沿 y = x + 1 翻折，其中 p 代表路径的第一个在 y = x + 1 上的点的横坐标。易知每一种不合法方案与翻折后的线段是一一对应的。考虑翻折后的线段的意义：从 (-1, 1) 到 (n, m) 的路径个数。显然为 \binom{n + m}{n + 1}。

故答案为 \binom{n + m}{n} - \binom{n + m}{n + 1}。

化简一下式子得到答案为 \dfrac{(n + m)!(n + 1 - m)}{(n + 1)!m!}

考虑到这题模数不是质数，不能直接求逆元。则通过枚举质数计算分子分母在该质数上的指数即可。

时间复杂度 O(\omega(n)\log P)。

#include <cstdio>
#include <cassert>
using namespace std;

typedef long long ll;

const int PRMCNT = 1348764 + 10, RANGE = 2000000 + 10, P = 20100501;

int n, m;
ll ans;
int prime[PRMCNT], cnt, not_prime[RANGE];

void getprime() {
    for (int i = 2; i <= 2000000; ++i) {
        if (!not_prime[i]){
            prime[++cnt] = i;
            for (int j = i + i; j <= 2000000; j += i) not_prime[j] = true;
        }
    }
}
int getnum(int p, int n) { // 一个有用的 trick，计算 n! 在质数 p 上的指数
    int ans = 0;
    while (n) n /= p, ans += n;
    return ans;
}
int qpower(int a, int x) {
    int ret = 1;
    for (; x; x >>= 1, a = 1ll * a * a % P) x & 1 ? ret = 1ll * ret * a % P : 0;
    return ret;
}

void solve() {
    ans = 1;
    scanf("%d %d", &n, &m);
    int nm = n + 1 - m;
    for (int i = 1; i <= cnt && prime[i] <= n + m; ++i) {
        int cur = 0;
        while (nm % prime[i] == 0) nm /= prime[i], cur ++;
        cur += getnum(prime[i], n + m), cur -= getnum(prime[i], n + 1), cur -= getnum(prime[i], m);
        ans = 1ll * ans * qpower(prime[i], cur) % P;
    }
    printf("%lld\n", ans);
}

int main() {
    getprime();
    int t; scanf("%d", &t);
    while (t --) solve();
    return 0;
}

坐标转换与组合计数！

还有一个高爸的回答，可以看看 :thinking: