![[…/data/img/e5e92bc7d32828b005d6b7f73694da57_720.jpg]]

素数筛 （欧拉筛）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> prime;
int mint[N];   // 最小素因子

void init() {
    for (int i = 2; i < N; i++) {
        if (!mint[i]) mint[i] = i, prime.push_back(i);
        for (auto& p : prime) {
            if (1ll * i * p >= N) break;
            mint[i * p] = p;
            if (p == mint[i]) break;
        }
    }
    mint[1] = 1;
}

时间复杂度Θ(n)\Theta(n)

VJwin6D - 又见GCD

题意 已知a, ba,~b，数cc 满足gcd⁡(a,c)=b\gcd(a,c)=b 且c≠bc\ne b，求cc 的最小值。

思路 设a=ba0, c=bc0a=ba_0,~c=bc_0，则gcd⁡(a0,c0)=1\gcd(a_0,c_0)=1，对a0a_0 作惟一分解a0=∏piαia_0=\prod p_i^{\alpha_i}，取最小的满足p0∤ap_0\nmid a 的p0p_0，则c=bp0c=bp_0 是所求的最小值。其中求p0p_0 可借助素数筛。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void eachT() {
    ll a, c;
    memset(isFactor, 0, sizeof isFactor);
    scanf("%lld %lld", &a, &c);
    a /= c;
    for (ll i = 2; i <= a; i++) {
        if (a % i == 0) isFactor[i] = true;
        while (a % i == 0) a /= i;
    }
    for (ll i = 2; i <= maxN; i++) {
        if (!isntPrime[i] && !isFactor[i]) {
            printf("%lld\n", c * i);
            return;
        }
    }
}

评注 枚举c=bi, i⩾2c=bi,~i\geqslant2，直至(a,c)=b(a,c)=b 即可。

1
2
3
4
scanf("%d %d", &a, &c);
b = 2 * c;
while (gcd(a, b) != c) b += c;
printf("%d\n", b);

质数距离

Description

给定两个整数LL 和UU，你需要在闭区间[L,U][L,U] 内找到距离最接近的两个相邻质数C1C_1 和C2C_2（C1<C2C_1 < C_2）（即C2−C1C_2-C_1 是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数D1D_1 和D2D_2（D1<D2D_1 < D_2）（即D2−D1D_2-D_1 是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

输入格式

每行输入两个整数LL 和UU，其中LL 和UU 的差值不会超过10610^6。

输出格式

对于每个LL 和UU，输出一个结果，结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）

如果LL 和UU 之间不存在质数对，则输出 There are no adjacent primes.。

数据范围

1≤L<U≤231−11 \le L < U \le 2^{31}-1

Notes

我们易知：对于每一个合数NN 都有一个小于等于N\sqrt{ N } 的因子
所以，对于L∼UL\sim U 中的所有合数，一定有一个1∼500001\sim50000 的因子
因此，我们先利用素数筛找出所有1∼500001\sim50000 的所有素数，再通过这些素数筛掉所有L∼UL\sim U 中的所有合数

Code

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 10;

bool isntPrime[N];
// vector<ll> prime;
ll prime[N];
ll cnt;
void doPrime(ll mx)
{
    cnt = 0;
    for (ll i = 2; i <= mx; i++)
    {
        if (!isntPrime[i])
            prime[++cnt] = i;

        for (int j = 1; j <= cnt; j++)
        {
            ll ps = prime[j];
            if (ps * i > mx)
                break;
            isntPrime[ps * i] = 1;
            if (i % ps == 0)
                break;
        }
    }
    isntPrime[1] = 1;
}

ll ps[N];
// ll st[N];
ll st[(ll)1e6 + 10];

signed main()
{
    doPrime(50000 + 10);
    ll l, r;
    while (~scanf("%lld%lld", &l, &r))
    {
        memset(st, 0, sizeof st);

        for (ll j = 1; j <= cnt; j++)
        {
            ll p1 = prime[j];
            ll x = max((l + (p1 - 1)) / p1 * p1, 2ll * p1);  // l/p向上取整再乘p，表示大于等于l的第一个p的倍数
            for (ll i = x; i <= r; i += p1)
            {
                st[i - l] = 1;
            }
        }

        ll cnt = 0;
        for (ll i = l; i <= r; i++)
        {
            if (st[i - l] == 0 && i > 1)
            {
                ps[++cnt] = i;
            }
        }

        if (cnt <= 1)
        {
            printf("There are no adjacent primes.\n");
            continue;
        }

        ll D1, D2;
        ll C1, C2;
        ll valmin = 1e6 + 10;
        ll valmax = 0;
        for (ll i = 1; i < cnt; i++)
        {
            if (ps[i + 1] - ps[i] < valmin)
            {
                C1 = ps[i], C2 = ps[i + 1];
                valmin = ps[i + 1] - ps[i];
            }
            if (ps[i + 1] - ps[i] > valmax)
            {
                D1 = ps[i], D2 = ps[i + 1];
                valmax = ps[i + 1] - ps[i];
            }
        }
        printf("%lld,%lld are closest, %lld,%lld are most distant.\n", C1, C2, D1, D2);
    }
}

VJwin14F - 终于结束的起点

题意 给定模MM，设斐波那契数列取模后为fib(n)\mathrm{fib}(n)，求最小的n>0n > 0，使得fib(n)=0, fib(n+1)=1\mathrm{fib}(n)=0,~ \mathrm{fib}(n + 1)=1。数据范围：2⩽M⩽10182 \leqslant M \leqslant 10^{18}。

思路 设n=f(M)n=f(M)，

暴力打表：

1
2
3
4
5
int f1 = 0, f2 = 1, f3;
for (int i = 1; i < INF; i++) {
    f3 = (f1 + f2) % M, f1 = f2, f2 = f3;
    if (f1 == 0 && f2 == 1) return i;
}

结果为：

1
2
3
4
5
6
7
8
9
10
 1 1     2 3     3 8     4 6     5 20
 6 24    7 16    8 12    9 24   10 60
11 10   12 24   13 28   14 48   15 40
16 24   17 36   18 24   19 18   20 60
21 16   22 30   23 48   24 24   25 100
26 84   27 72   28 48   29 14   30 120
31 30   32 48   33 40   34 36   35 80
36 24   37 76   38 18   39 56   40 60
41 40   42 48   43 88   44 30   45 120
46 48   47 32   48 24   49 112  50 300

观察得出：

  • f(x2)=xf(x)f(x^2)=xf(x)，f(xn)=xn−1f(x)f(x^n)=x^{n-1}f(x)；
  • 若p,qp,q 为素数，则f(pq)=f(p)f(q)f(pq)=f(p)f(q)，f(pmqn)=lcm[f(pm), f(qn)]f(p^mq^n)=\mathrm{lcm}\big[f(p^m),~f(q^n)\big]；

因此，设M=p1α1p2α2…pnαnM=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_n^{\alpha_n}​，则

\begin{align} f(M) &=\mathrm{lcm}\big[ f(p_1^{\alpha_1}),~ f(p_2^{\alpha_2}),~\dots,~ f(p_n^{\alpha_n})\big] \\ &=\mathrm{lcm}\big[ p_1^{\alpha_1-1}f(p_1),~ p_2^{\alpha_2-1}f(p_2),~\dots,~ p_n^{\alpha_n-1}f(p_n)\big] \end{align}

便可求出结果。

1
2
3
4
5
6
7
8
9
10
intread(M);
int ans = 1;
for (int p = 2; p <= M; ++p) {
    if (!(M % p)) {
        int times = 0;
        while (!(M % p)) ++times, M /= p;
        ans = lcm(ans, solve(p) * qpow(p, times - 1));
    }
}
printf("%d\n", ans);

其中 solve() 函数就是刚才的暴力打表函数，其复杂度不确定，最坏情况是Θ(M2)\Theta(M^2)。

输入 1000000009，程序运行 4.25s，超时。

对于很大的素数，时间复杂度可能很大，仍需优化。

优化 首先寻找fib(n)=0\mathrm{fib}(n)=0，设t=fib(n+1)t=\mathrm{fib}(n+1)，那么只需找到最小的mm，使得tm≡1t^m \equiv 1，答案即是mnmn。

证明：熟知，由于fib(n)=0\mathrm{fib}(n)=0，那么fib(mn)=0\mathrm{fib}(mn)=0，由于t=fib(n+1)t=\mathrm{fib}(n+1)，那么fib(2n+1)=t2\mathrm{fib}(2n+1)=t^2，fib(mn+1)=tm\mathrm{fib}(mn+1)=t^m，因此满足tm≡1t^m \equiv 1 的mm 即是所求。

时间复杂度最坏情况是Θ(M)\Theta(M)。

1
2
3
4
5
6
7
8
9
10
11
12
int f1 = 0, f2 = 1, f3;
for (int i = 1; ; i++) {
    f3 = (f1 + f2) % M, f1 = f2, f2 = f3;
    if (f1 == 0) {
        if (f2 == 1) return i;
        ll t = 1;
        for (int j = 1; ; ++j) {
            t = (t * f2) % M;
            if (t % M == 1) return i * j;
        }
    }
}

输入 1000000009，程序运行 1.45s……

勒让德定理

VJwin6H - 阶乘之乘

题意 求M=1!×2!×3!×4!×⋯×n!M=1!\times 2!\times 3!\times 4!\times \cdots \times n! 的末尾的00 的个数。

思路 由于MM 的标准分解中22 出现的次数一定多于55，只需求由55 在MM 中的指数。

勒让德定理：在n!n! 中素数pp 的指数

vp(n!)=∑k=1pk≤n⌊npk⌋=n−Sp(n)p−1.v_p(n!)=\displaystyle\sum\limits_{k=1}^{p^k\le n}\bigg\lfloor\dfrac{n}{p^k}\bigg \rfloor=\dfrac{n-S_p(n)}{p-1}.

其中，Sp(n)S_p(n) 表示nn 在pp 进制下各个位数的和，熟知

Sp(n)={1,if n=1Sp(np),if p∣nSp(n−1)+1,otherwise.S_p(n)= \begin{cases} 1, & \text {if } n=1 \\ \displaystyle S_p\Big(\frac{n}{p}\Big), & \text {if } p\mid n \\ S_p(n-1)+1, & \text {otherwise}. \end{cases}

思路一 利用勒让德定理的第二个形式，打表计算Sp(n)S_p(n)：

1
2
3
4
5
6
7
8
9
10
ll ans = 1;
vector<ll> a;
a.push_back(0ll); a.push_back(1ll);
for (ll i = 2; i <= n; i++) {
    if (i % 5) a.push_back(a[i - 1] + 1);
    else a.push_back(a[i / 5]);
    ans += a[i];
}
ans = (n * (n + 1) / 2 - ans) / 4;
printf("%lld\n", ans);

喜提MLE\mathbf{MLE}，改成 map 报TLE\rm{TLE}…… 1e8 的数据真的很难处理。

思路二 利用勒让德定理的第一个形式，稍作变形：

\begin{align} {\rm ans} &= \sum_{i=1}^{n}v_5(i!) = \sum_{i=1}^{n}\sum_{k=1}^{5^k\le i}\bigg\lfloor\dfrac{i}{5^k}\bigg\rfloor = \sum_{k=1}^{5^k\le n}\sum_{i=1}^{n}\bigg\lfloor\dfrac{i}{5^k}\bigg\rfloor \\ &= \sum_{k=1}^{5^k\le n}\bigg[ 5^k +2\cdot5^k +\dots +\bigg(\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor-1\bigg)\cdot5^k +\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\Big(n\bmod{5^k}+1\Big) \bigg] \\ &= \sum_{k=1}^{5^k\le n}\bigg[ \frac{5^k}{2}\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\bigg(\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor-1\bigg) +\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\Big(n\bmod{5^k}+1\Big) \bigg] \\ &= \sum_{5\le i=5^k\le n}^{}\bigg[ \frac{i}{2}\bigg\lfloor\dfrac{n}{i}\bigg\rfloor\bigg(\bigg\lfloor\dfrac{n}{i}\bigg\rfloor-1\bigg) +\bigg\lfloor\dfrac{n}{i}\bigg\rfloor\Big(n\bmod{i}+1\Big) \bigg] \\ \end{align}

时间复杂度Θ(log⁡n)\Theta(\log n)。

1
2
3
4
5
6
ll ans = 0;
for (int i = 5; i <= n; i *= 5) {
    ans += (ll)i * (n / i) * (n / i - 1) >> 1;
    ans += (n / i) * (n % i + 1);
}
printf("%lld\n", ans);

质因数分解

算术基本定理：任何一个大于11 的正整数都能唯一分解为有限个质数的乘积

N=p1c1p2c2…pmcmN = p_{1}^{c_{1}}p_{2}^{c_{2}}\dots p_{m}^{c_{m}}

推论1：NN 的正约数的个数为

∏i=1m(ci+1)=(c1+1)(c2+1)⋯(cm+1)\prod_{i=1}^{m}(c_{i}+1)=(c_{1}+1)(c_{2}+1)\cdots(c_{m}+1)

推论2：NN 的所有正约数的和为

(1+p1+p12+⋯+p1c1)⋯(1+pm+pm2+⋯+pmcm)(1+p_{1}+p_{1}^{2}+\dots+p_{1}^{c_{1}})\cdots(1+p_{m}+p_{m}^{2}+\dots+p_{m}^{c_{m}})

质数定理：1∼n1\sim n 中的质数个数约为nln⁡(n)\cfrac{n}{\ln(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
// 质因数分解
auto getfactor(int x) {
    vector<array<int, 2>> res;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            int cnt = 0;
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
            res.push_back({ i, cnt });
        }
    }
    if (x > 1) res.push_back({ x, 1 });
    return move(res);
}

// 枚举约数
auto getdivisor(int x) {
    auto factor = getfactor(x);
    vector<array<int, 2>> res;
    auto dfs = [&](this auto&& self, int x, int sum, int id) -> void {
        if (id == factor.size()) {
            res.push_back({ x, sum });
        } else for (int i = 0; i <= factor[id][1]; i++) {
            self(x, sum + i, id + 1);
            x *= factor[id][0];
        }
    };
    dfs(1, 0, 0);
    sort(res.begin(), res.end());
    return move(res);
}

时间复杂度：O(N)O(\sqrt{ 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
bool isntPrime[N];
vector<int> prime;
void doPrime(int mx)
{
    for (int i = 2; i <= mx; i++)
    {
        if (!isntPrime[i])
            prime.push_back(i);
        for (auto p : prime)
        {
            if (p * i > mx)
                break;
            isntPrime[p * i] = 1;
            if (i % p == 0)
                break;
        }
    }
    isntPrime[1] = 1;
}

int p[N];
int c[N];
int m;

void divide(int n)
{
    cout << n << " = ";
    m = 0;
    for (auto ps : prime)
    {
        if (ps * ps > n)
            break;
        if (n % ps == 0)
        {
            p[++m] = ps, c[m] = 0;
            while (n % ps == 0)
                n /= ps, c[m]++;
        }
    }
    if (n > 1)
    {
        p[++m] = n;
        c[m] = 1;
    }
    for (int i = 1; i <= m; i++)
    {
        cout << p[i] << "^" << c[i] << " ";
    }
    cout << endl;
}

不算欧拉筛的处理，时间复杂度O(2Nln⁡n)O(\cfrac{2\sqrt{ N }}{\ln n})

BUC1B 三角形数

题意 求第一个约数数量大于500500 的三角形数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int numOfDivisors(int x) {
    int ans = 1;
    for (int i = 2; i * i <= x; i++) {
        int r = 0;
        while (x % i == 0) ++r, x /= i;
        if (r) ans *= r + 1;
    }
    if (x > 1) ans *= 2;
    return ans;
}

void eachT() {
    int p = 1;
    for (int i = 2; ; i++) {
        if (numOfDivisors(p) > 500) {
            printf("%d\n", p);
            break;
        }
        p += i;
    }
}

答案 76576500，约 19ms。

枚举一个数的约数

1
2
3
4
5
6
7
8
9
10
vector<ll> factor(ll x) {
    vector<ll> d;
    for (ll i = 1; i * i <= x; i++) {
        if (x % i) continue;
        d.push_back(i);
        if (i != x / i) d.push_back(x / i);
    }
    sort(d.begin(), d.end());
    return d;
};

VJwin6J - Sumdiv

（模板）求aba^{b} 的因子和：

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
#include <cstdio>
#include <algorithm>
using ll = long long;
constexpr int MOD = 9901;
inline ll read() {
    ll S = 0, C = 0; char Y = getchar();
    while (Y > 57 || Y < 48) C |= Y == 45, Y = getchar();
    while (Y <= 57 && Y >= 48) S = (S << 3) + (S << 1) + Y - 48, Y = getchar();
    return C ? -S : S;
}

ll qpow(ll a, ll n) {
    ll ans = 1;
    while (n) {
        if (n & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return ans;
}

ll qq(ll a, ll n) {
    if (n == 1) {
        return 1;
    }
    else if (n & 1) {
        return (qq(a, n - 1) + qpow(a, n - 1)) % MOD;
    }
    else {
        return qq(a, n / 2) * (qpow(a, n / 2) + 1) % MOD;
    }
}

int main() {
    ll a = read(), b = read();

    if (a == 0) printf("0\n");
    else if (a == 1) printf("1\n");
    else if (b == 0) printf("1\n");
    else {
        ll ans = 1;
        for (ll i = 2; i <= a; i++) {
            if (a % i) continue;
            ll cnt = 0;
            while (a % i == 0) {
                ++cnt;
                a /= i;
            }
            ans = ans * qq(i % MOD, (cnt * b + 1)) % MOD;
        }
        printf("%lld\n", ans);
    }

    return 0;
}

2024 杭电多校 8007 - cats 的 k-xor

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
#include <cstdio>
using ll = long long;
inline ll read() {
    ll S = 0, C = 0; char Y = getchar();
    while (Y > 57 || Y < 48) C |= Y == 45, Y = getchar();
    while (Y <= 57 && Y >= 48) S = (S << 3) + (S << 1) + Y - 48, Y = getchar();
    return C ? -S : S;
}

void eachT() {
    int a = read(), b = read(), c = read();

    int v = a + b - c;
    int ans = 0;

    if (v < 0) {
        ans = 0;
    }
    else if (v == 0) {
        ans = -1;
    }
    else {
        auto solve = [&](int a, int b, int c, int x) {
            while (a || b || c) {
                if ((a % x + b % x) % x != c % x) return 0;
                a /= x, b /= x, c /= x;
            }
            return 1;
        };
        for (int i = 2; 1ll * i * i <= v; i++) {
            if (v % i == 0) {
                ans += solve(a, b, c, i);
                if (i != v / i) ans += solve(a, b, c, v / i);
            }
        }
        if (v > 1) ans += solve(a, b, c, v);
    }

    printf("%d\n", ans);
}

int main() {
    for (int T = read(); T--; eachT());
    return 0;
}

VJwin6F - Revenge of GCD

题意 求两个数的第kk 大公约数。

思路 即是它们最大公约数的第kk 大约数。枚举所有约数，再排序即可。

VJwin6E - GCD Arrays

题意 一个由连续正整数组成的数列A={l, l+1, …, r}A=\{l,~l+1,~\dots,~r\}，至多有kk 次机会将两个数以它们的乘积替代，能否使gcd⁡A≠1\gcd A\ne1。

思路 记数列的项数为nn。

当nn 为偶数时，一方面，AA 中不能有相邻两个自然数，故至少要操作n2\frac{n}{2} 次；另一方面，操作相邻两个奇数和偶数，共需n2\frac{n}{2} 次，此时gcd⁡A=2\gcd A=2。

当nn 为奇数时，同样地，至少操作n−12\frac{n-1}{2} 次，若l,rl,r 都是偶数，操作后全是偶数，此时gcd⁡A=2\gcd A=2，但若l,rl,r 都是奇数，操作后至少留下一个奇数，gcd⁡A=1\gcd A=1，需要再操作一次。

VJwin14B - Hankson 的趣味题

题意 已知gcd⁡(x,a0)=a1, lcm(x,b0)=b1\gcd(x,a_0)=a_1,~\mathrm{lcm}(x,b_0)=b_1，求满足条件的xx 的个数。

思路 考虑每一个素数pp，设pγ∥x, pα0∥a0, pα1∥a1, pβ0∥b0, pβ1∥b1p^{\gamma}\parallel x,~p^{\alpha_0}\parallel a_0,~p^{\alpha_1}\parallel a_1,~p^{\beta_0}\parallel b_0,~p^{\beta_1}\parallel b_1，题设等价于min⁡(γ,α0)=α1, max⁡(γ,β0)=β1\min(\gamma,\alpha_0)=\alpha_1,~\max(\gamma,\beta_0)=\beta_1。

为了知道γ\gamma 的存在性，我们对四个字母作讨论：

如果α0>α1∧β0<β1\alpha_0>\alpha_1\land \beta_0<\beta_1，则γ\gamma 存在  ⟺  α1=β1\iff\alpha_1=\beta_1，且只能取γ=α1\gamma=\alpha_1；

如果α0>α1∧β0=β1\alpha_0>\alpha_1\land \beta_0=\beta_1，则γ\gamma 存在  ⟺  α1⩽β1\iff\alpha_1\leqslant\beta_1，且只能取γ=α1\gamma=\alpha_1；

如果α0=α1∧β0<β1\alpha_0=\alpha_1\land \beta_0<\beta_1，则γ\gamma 存在  ⟺  α1⩽β1\iff\alpha_1\leqslant\beta_1，且只能取γ=β1\gamma=\beta_1；

如果α0=α1∧β0=β1\alpha_0=\alpha_1\land \beta_0=\beta_1，则γ\gamma 存在  ⟺  α1⩽β1\iff\alpha_1\leqslant\beta_1，且γ\gamma 可以取[α1,β1][\alpha_1,\beta_1] 中任意整数，共β1−α1+1\beta_1-\alpha_1+1 种选择。

考虑所有的素数pp，利用乘法原理即得答案。

1
2
3
4
5
6
7
8
9
10
11
void solve(int p) {
    int pa0 = 0, pa1 = 0, pb0 = 0, pb1 = 0;
    while (!(a0 % p)) ++pa0, a0 /= p;
    while (!(a1 % p)) ++pa1, a1 /= p;
    while (!(b0 % p)) ++pb0, b0 /= p;
    while (!(b1 % p)) ++pb1, b1 /= p;
    if (pa0 > pa1 && pb0 < pb1) ans *= pa1 == pb1;
    else if (pa0 > pa1 && pb0 == pb1) ans *= pa1 <= pb1;
    else if (pa0 == pa1 && pb0 < pb1) ans *= pa1 <= pb1;
    else ans *= (pa1 <= pb1) * (pb1 - pa1 + 1);
}

有一个问题是素数pp 的选择，我们使用素数筛找出在范围内的素数。注意，筛素数时只需筛出⩽maxN\leqslant\sqrt{\rm maxN} 的素数，以减小时间复杂度，但仍需考虑所给本身是个大素数的情形，因此在自除后，如果仍有a0′>1∨b1′>1a_0'>1\lor b_1'>1，就说明它本身是个大素数，需要取p=a0′p=a_0'（或b1′b_1'）重複上述过程。

因此主函数的写法是：

1
2
3
4
5
6
scanf("%d %d %d %d", &a0, &a1, &b0, &b1);
ans = 1;
for (int i = 0; i < cntPrime; i++) solve(prime[i]);
if (a0 > 1) solve(a0);
else if (b1 > 1) solve(b1);
printf("%lld\n", ans);

评注 根据gcd⁡(x,a0)=a1, lcm(x,b0)=b1\gcd(x,a_0)=a_1,~\mathrm{lcm}(x,b_0)=b_1，设x=x′a1, a0=a0′a1, b1=x′′x, b1=b0′b0x=x'a_1,~a_0=a_0'a_1,~b_1=x''x,~b_1=b_0'b_0，有b1=a1x′x′′b_1=a_1x'x''，再令n=x′x′′n=x'x''，即x′′=nx′x''=\frac{n}{x'}，则(x′,a0′)=1, (nx′,b0′)=1(x',a_0')=1,~(\frac{n}{x'},b_0')=1（结论一）

我们枚举nn 的约数x1x_1，带入检验(x′,a0′)=1(x',a_0')=1 是否成立，复杂度为Θ(b0′nlog⁡n)\Theta(b_0'\sqrt n\log n)。

优化 因为(nx′,b0′)=1(\frac{n}{x'},b_0')=1，故nx′\frac{n}{x'} 与b0′b_0' 没有相同的素因子，将nn 与b0′b_0' 所有相同的素因子从nn 中去掉，得到n′n'，能够证明，nx′∣n′\frac{n}{x'}\mid n'，它等价于nn′∣x′\frac{n}{n'}\mid x'，

可设x′=nn′rx'=\frac{n}{n'}r，结合(x′,a0′)=1(x',a_0')=1，知而rr 也必须是n′n' 的约数。于是就又有：

r∣n′,(r,a0′)=1r|n',(r,a_0')=1（结论二）

我们可以用与解决结论一相似的方法，将n′n' 与nn 所有相同的质因数从n′n' 中去掉，得到剩余的数qq。那么这样，所有符合条件的rr 都是qq 的因数了。然后，我们可以用枚举qq 的所有因数，输出 $q $ 的因数个数就行了。这样，复杂度便降到了：O((lqrn(n′n' )+log(n′n' ))*t)，从理论来说也不会超时了。

还有一点需要注意，那就是特判没有符合要求的x的情况。这种情况出现只有四种可能：

1、n′n' 不为整数

2、a_0’不为整数

3、b_0’不为整数

4、(nn′\frac{n}{n'} ,s)≠1，即因为x′x' 是l/l的倍数，所以无论r取何值，都会有(m,s)≠1

加上这四个特判，这道题便做完了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int removeCommonP(int a, int b) {
    for (int i = 2; i * i <= b; i++) {
        if (!(b % i)) while (!(a % i)) a /= i;
        while (!(b % i)) b /= i;
    }
    if (b != 1) while (!(a % b)) a /= b;
    return a;
} // 去掉a中与b共有的素因子

void eachT() {
    int a0, a1, b0, b1;
    scanf("%d %d %d %d", &a0, &a1, &b0, &b1);
    if (a0 % a1 || b1 % b0 || b1 % a1) {printf("0\n");return;}
    a0 = a0 / a1, b0 = b1 / b0, a1 = b1 / a1;
    int n1 = removeCommonP(a1, b0);
    if (gcd(a1 / n1, a0) != 1) {printf("0\n");return;}
    int n2 = removeCommonP(n1, a0);
    printf("%d\n", numOfDivisors(n2));
}

CF919C. Partitioning the Array

题意 给出一个数列，将数量按序划分为长度均为kk 的子列，且在某个模mm 下所有子列全相等（定义为对应位置相等），求划分的种数。

思路 有两个数需要确定：

一是子列长度kk。它是总元素个数的约数，容易枚举：

1
2
3
4
5
6
for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        if (i * i == n) ans += sol(i);
        else ans += sol(i) + sol(n / i);
    }
}

二是模mm。这里介绍一种确定模的方法：

对于模mm，在模mm 下所有子列对应位置全相等，即

a1=ak+1=a2k+1=⋯(modm)a2=ak+2=a2k+2=⋯(modm)⋯⋯ak=   a2k=   a3k=⋯(modm)\begin{aligned} a_1=a_{k+1}=a_{2k+1}=\cdots \pmod m \\ a_2=a_{k+2}=a_{2k+2}=\cdots \pmod m \\ \cdots\cdots \\ a_k=~~~a_{2k}=~~~a_{3k}=\cdots \pmod m \end{aligned}

先从简单的情况入手，如果a=b(modm)a=b\pmod m，会得出什么？比如有模的定义式m∣b−am \mid b-a，我们根据a−ba-b 枚举就能确定mm；

那三个数a=b=c(modm)a=b=c\pmod m 呢？我们有m∣b−am \mid b-a 和m∣c−bm \mid c-b，这表明，m∣gcd⁡(b−a, c−b)m \mid \gcd(b-a,~ c-b)（公约数是最大公约数的约数）；

以此类推，推广到很多数的情形，根据第一行的式子，能够得到

m∣gcd⁡(ak+1−a1, a2k+1−ak+1, … ),m \mid\gcd(a_{k+1}-a_1,~a_{2k+1}-a_{k+1},~\dots),

进而，结合其它几行，

m∣gcd⁡(ak+1−a1, a2k+1−ak+1, …, ak+2−a2, a2k+2−ak+2, …, … ),m \mid\gcd(a_{k+1}-a_1,~a_{2k+1}-a_{k+1},~\dots,~a_{k+2}-a_2,~a_{2k+2}-a_{k+2},~\dots,~\dots),

整理一下便是

m∣gcd⁡(ak+1−a1, ak+2−a2, …, an−an−k),m \mid\gcd(a_{k+1}-a_{1},~a_{k+2}-a_{2},~\dots,~a_{n}-a_{n-k}),

我们可以先计算后面一长串式子，取mm​ 为这个数即可，注意题目要求，m≥2m\ge2​，因此若结果等于11​，表明mm​​ 不存在。

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
#include <cstdio>
#include <algorithm>
const int maxN = 2e5 + 7;
int n, ans, a[maxN];

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

bool sol(int k) {
    int m = 0;
    for (int i = 1; i <= n - k; i++) {
        m = gcd(m, abs(a[i + k] - a[i]));
    }
    return m != 1;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                if (i * i == n) {
                    ans += sol(i);
                }
                else {
                    ans += sol(i);
                    ans += sol(n / i);
                }
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}

CF921B. A Balanced Problemset

题意 给定x,kx,k，令x=a1+a2+⋯+akx=a_1+a_2+\dots+a_k，给出一种拆分方法，使m=gcd⁡am=\gcd a 最大。

思路 注意到，m⩽min⁡a⩽xkm\leqslant\min a\leqslant\frac{x}{k}，且m ∣ ai⇒m ∣ xm~|~a_i\Rightarrow m~|~x，故mm 是xx 的不大于xk\frac{x}{k} 的最大约数。

1
2
3
4
5
6
7
8
int n = read(), k = read(), ans = 0;
for (int i = 1; i <= n / i; i++) {
    if (n % i == 0) {
        if (i >= k) ans = max(ans, n / i);
        if (i <= n / k) ans = max(ans, i);
    }
}
print(ans);

枚举 1 ~ N 每个数的约数

1
2
3
4
5
6
7
8
vector<int> fac[N];
void init() {
    for (int i = 1; i < N; i++) {
        for (int j = 1; i * j < N; j++) {
            fac[i * j].push_back(i);
        }
    }
}

时间复杂度：O(N+N2+N3+⋯+NN)=O(Nlog⁡N)O(N+\cfrac{N}{2}+\cfrac{N}{3}+\dots+\cfrac{N}{N})=O(N\log N)

两个推论：

  1. 一个整数NN 的约数个数上界为2N2\sqrt{ N }
  2. 1∼N1\sim N 每个数的约数个数的总和大约为Nlog⁡NN\log N

例：[[…/图论 - 树/树习题集#2024 杭电多校 3001 - 深度自同构|2024 杭电多校 3001 - 深度自同构]]

枚举 L ~ R 每个数的约数

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
struct Sieve {
    vector<int> prime;
    vector<int> isntPrime;

    void init(int N) {
        isntPrime.resize(N + 1);
        for (int i = 2; i <= N; i++) {
            if (!isntPrime[i]) prime.push_back(i);
            for (auto& p : prime) {
                if (1ll * i * p > N) break;
                isntPrime[i * p] = 1;
                if (i % p == 0) break;
            }
        }
        isntPrime[1] = 1;
    }
} sieve;

struct Divisor {
    ll L, R, len;
    vector<int>& prime = sieve.prime;
    vector<vector<pll> > primeFactor;

    void cal(ll num, ll d);

    void init() {
        vector<ll> a(len);
        for (ll i = 0; i < len; i++) a[i] = L + i;

        primeFactor.resize(len);

        for (auto& p : prime) {
            if (1ll * p * p > R) break;
            for (ll i = (-L % p + p) % p; i < len; i += p) {
                if (a[i] % p) continue;
                int c = 0;
                while (a[i] % p == 0) a[i] /= p, ++c;
                primeFactor[i].emplace_back(p, c);
            }
        }

        for (ll i = 0; i < len; i++) {
            if (a[i] > 1) primeFactor[i].emplace_back(a[i], 1);
        }
    }

    vector<ll> factor(ll x) {
        vector<ll> d;

        d.push_back(1);
        for (auto& [p, c] : primeFactor[x]) {
            ll siz = d.size();
            for (ll i = 0, pow = p; i < c; i++, pow *= p) {
                for (ll k = 0; k < siz; ++k)
                    d.push_back(d[k] * pow);
            }
        }

        return d;
    }

    void solve(ll l, ll r) {
        L = l, R = r, len = R - L + 1;

        init();
        for (ll i = 0; i < len; i++) {
            for (auto& d : factor(i)) cal(i, d);
        }
    }
};

void Divisor::cal(ll num, ll d) {
    // do something
}

int main() {
    sieve.init(1000000);

    Divisor div;
    div.solve(L, R);
}

时间复杂度Θ(R+∑d(i))\Theta\left( \sqrt{ R } + \sum d(i) \right)，其中d(i)d(i) 表示ii 的约数个数。

2024 牛客多校 8E - Haitang and Math

[[…/contests/2024牛客多校/2024-08-08：2024牛客暑期多校训练营8|2024-08-08：2024牛客暑期多校训练营8]]

题意 给定nn，满足如下条件的mm 的数量：

  • 1⩽m⩽n1 \leqslant m \leqslant n；
  • n mod mn\bmod m 等于mm 的数码和S(m)S(m)。

思路 枚举S(m)S(m)，再枚举mm，逐个检验。

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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
constexpr int N = 1e6 + 8;
inline ll read() {
    ll S = 0, C = 0; char Y = getchar();
    while (Y > 57 || Y < 48) C |= Y == 45, Y = getchar();
    while (Y <= 57 && Y >= 48) S = (S << 3) + (S << 1) + Y - 48, Y = getchar();
    return C ? -S : S;
}

struct Sieve { ... } sieve;

struct Divisor { ... };

void beforeT() {
    sieve.init(1000000);
}

// 获取数码和
int getDigitSum(ll x) {
    int sum = 0;
    while (x) sum += x % 10, x /= 10;
    return sum;
}

ll n;
vector<ll> res;
void Divisor::cal(ll num, ll d) {
    if (n % d == getDigitSum(d)) {
        res.push_back(d);
    }
}

void eachT() {
    n = read();
    vector<ll>().swap(res);

    Divisor div;
    div.solve(max(1ll, n - 108), n);

    sort(res.begin(), res.end());
    int siz = unique(res.begin(), res.end()) - res.begin();
    printf("%d\n", siz);
}

int main() {
    beforeT();
    for (int T = read(); T--; eachT());
    return 0;
}

赛时写法如下，保证计数不重，但暂不知原理：

1
2
3
4
5
6
7
8
9
10
11
12
void Divisor::cal(ll num, ll d) {
    if (d >= 10 && getDigitSum(d) == R - L - num) {
        sum += 1;
    }
}

void eachT() {
    ll n = read();
    sum = 0;
    div.solve(max(1ll, n - 108), n);
    printf("%lld\n", sum);
}

反素数

Description

对于任何正整数xx，其约数的个数记作g(x)g(x)，例如g(1)=1、g(6)=4g(1)=1、g(6)=4。

如果某个正整数xx 满足：对于任意的小于xx 的正整数ii，都有g(x)>g(i)g(x)>g(i)，则称xx 为反素数。

例如，整数1，2，4，61，2，4，6 等都是反素数。

现在给定一个数NN，请求出不超过NN 的最大的反素数。

输入格式

一个正整数NN。

输出格式

一个整数，表示不超过NN 的最大反素数。

数据范围

1≤N≤2∗1091 \le N \le 2*10^9

输入样例：

1
1000

输出样例：

1
840

Notes

注意到：

  1. 对于一个NN ,设答案为xx ,那么xx 的约数一定是1∼N1\sim N 中最多的
  2. 若有yy 的约数与xx 的约数一样多，那么一定有x<yx<y
  3. 设x=p1c1p2c2…pmcmx=p_{1}^{c_{1}}p_{2}^{c_{2}}\dots p_{m}^{c_{m}} ，一定有c1⩾c2⩾⋯⩾cmc_{1} \geqslant c_{2} \geqslant \dots \geqslant c_{m}
  4. xx 的质因子pp 只会在2,3,5,7,11,13,17,19,232,3,5,7,11,13,17,19,23 中取，
    因为2∗3∗5∗7∗11∗13∗17∗19∗23∗292*3*5*7*11*13*17*19*23*29 已经大于2e92e^{9}

那么，我们就可以用 dfs 枚举
经过测试，哪怕n=2e9n=2e^{9} , 枚举次数也仅为14511451 次

Code

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
ll ps[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};

int x;
int num = -1;

void dfs(int u, int pre, int p, int s) // u:枚举的位置 pre:上个的指数 p:数的大小 s:约数个数
{
    if (u == 9)
        return;

    if (s > num || (s == num && p < x))
    {
        num = s;
        x = p;
    }
    for (int i = 1; i <= pre; i++)
    {
        if (p * ps[u] > n)
            break;

        p *= ps[u];
        dfs(u + 1, i, p, s * (i + 1));
    }
}

int main()
{
    cin >> n;
    dfs(0, 30, 1, 1);
    cout << x << endl;
}

余数之和

Description

给出正整数nn 和kk，计算j(n,k)=k mod 1+k mod 2+k mod 3+…+k mod nj(n, k)=k \bmod 1 + k \bmod 2 + k \bmod 3 + … + k \bmod n 的值。

例如j(5,3)=3 mod 1+3 mod 2+3 mod 3+3 mod 4+3 mod 5=0+1+0+3+3=7j(5, 3)=3 \bmod 1 + 3 \bmod 2 + 3 \bmod 3 + 3 \bmod 4 + 3 \bmod 5=0+1+0+3+3=7。

输入格式

输入仅一行，包含两个整数n,kn, k。

输出格式

输出仅一行，即j(n,k)j(n, k)。

数据范围

1≤n,k≤1091 \le n,k \le 10^9

Notes

∑i=1nk mod i=n∗k−∑i=1n⌊k/i⌋∗i\sum_{i = 1}^{n} k \bmod i = n * k - \sum_{i = 1}^{n} \lfloor k / i \rfloor * i

显然，⌊k/i⌋\lfloor k / i \rfloor 是最棘手的，我们要想办法简化计算。

证明单调性

  • 观察⌊k/i⌋\lfloor k / i \rfloor，显然随着ii 的增大，这个式子是越来越小的。

  • 又因为有向下取整符号，所以该式子取值只能是整数。

若我们设函数f(x)=⌊k/x⌋f(x) = \lfloor k / x \rfloor。则画在坐标轴中应该是从高到低一条条横线。

上图是一条f(x)=⌊10/x⌋f(x) = \lfloor 10 / x \rfloor 的图像。

证明该式子最多只有2k2\sqrt{k} 个取值

分段讨论：

  • 当i<=ki <= \sqrt{k} 时，因为ii 是11 到k\sqrt{k} 的整数，所以最多只有k\sqrt{k} 个不同的⌊k/i⌋\lfloor k / i \rfloor 值。
  • 当i>ki > \sqrt{k} 时，⌊k/i⌋<=k\lfloor k / i \rfloor <= \sqrt{k}，又因为式子取整了，所以式子只能取11 到k\sqrt{k} 的整数，故最多也只有k\sqrt{k} 个不同的⌊k/i⌋\lfloor k / i \rfloor 值。

综上所述，⌊k/i⌋\lfloor k / i \rfloor 最多只有2k2\sqrt{k} 个取值

有关 当i>ki > \sqrt{k} 时，⌊k/i⌋<=k\lfloor k / i \rfloor <= \sqrt{k} 的证明：

由于下取整，所以⌊k/i⌋∗i<=k\lfloor k / i \rfloor * i <= k ①

假设 $\lfloor k / i \rfloor > \sqrt{k} $，有⌊k/i⌋∗i>⌊k/i⌋∗k>k2=k\lfloor k / i \rfloor * i > \lfloor k / i \rfloor * \sqrt{k} > \sqrt{k} ^ 2 = k。②

① 与 ② 矛盾

通过以上步骤，我们可以知道这个答案由连续2k2\sqrt{k} 段不同的取值组成，那么我们只需要确定每种取值是下界ll 和 上界rr。通过∑i=lr⌊k/i⌋∗i=∑i=lr⌊k/l⌋∗i=⌊k/l⌋∗(∑i=lri)\sum_{i = l}^{r} \lfloor k / i \rfloor * i = \sum_{i = l}^{r} \lfloor k / l \rfloor * i = \lfloor k / l \rfloor * (\sum_{i = l}^{r}i) 即可求得每一段对答案的贡献。(∑i=lri)(\sum_{i = l}^{r}i) 可以用等差数列求和公式计算。

已知下界求上界

假设我们知道一段相同取值的下界是xx，若能求出上界，我们问题便解决了。

猜想若下界是xx，上界是r=⌊k/⌊k/x⌋⌋r = \lfloor k / \lfloor k / x \rfloor \rfloor

第一步、求证⌊k/x⌋=⌊k/r⌋\lfloor k / x \rfloor = \lfloor k / r \rfloor

  • 由定义式可知r∗⌊k/x⌋+q=kr * \lfloor k / x \rfloor + q = k ③，其中0<=q<⌊k/x⌋0 <= q < \lfloor k / x \rfloor，所以⌊k/r⌋=⌊r∗⌊k/x⌋+qr⌋=⌊k/x⌋+⌊qr⌋>=⌊k/x⌋\lfloor k / r \rfloor = \lfloor\frac{r * \lfloor k / x \rfloor + q}{r}\rfloor = \lfloor k / x \rfloor + \lfloor \frac{q}{r} \rfloor >= \lfloor k / x \rfloor

  • r>=⌊k/(k/x)⌋=xr >= \lfloor k / (k / x ) \rfloor = x，所以⌊k/x⌋>=⌊k/r⌋\lfloor k / x \rfloor >= \lfloor k / r \rfloor

综上⌊k/x⌋=⌊k/r⌋\lfloor k / x \rfloor = \lfloor k / r \rfloor。

第二步、求证⌊k/(r+1)⌋≠⌊k/x⌋\lfloor k / (r + 1) \rfloor \not = \lfloor k / x \rfloor

假设⌊k/(r+1)⌋=⌊k/x⌋\lfloor k / (r + 1) \rfloor = \lfloor k / x \rfloor

那么有(r+1)∗⌊k/x⌋+q’=k(r + 1) * \lfloor k / x \rfloor + q’ = k，其中0<=q<r+10 <= q < r + 1

把式子变化一下：

$r * \lfloor k / x \rfloor + \lfloor k / x \rfloor + q’ = k $ ④

③④ 联立，有：

⌊k/x⌋+q’<⌊k/x⌋\lfloor k / x \rfloor + q’ < \lfloor k / x \rfloor

因为q’>=0q’ >= 0，所以该式子矛盾，故假设不成立。

通过这两步及之前的单调性，我们知道⌊k/⌊k/x⌋⌋\lfloor k / \lfloor k / x \rfloor \rfloor 一定是上界

算法

所以算法就很好设计了：

  • 设l=1l = 1，算出上界rr。计算这段的贡献
  • 使l=r+1l = r + 1，即跳到下一段计算贡献。
  • 重复知道算完[1,n][1, n] 里所有段。

Tips:Tips:

  1. 当⌊k/l⌋=0\lfloor k / l \rfloor = 0 的时候，显然这段以及后面（有单调性）已经没有贡献了，可以breakbreak。（或者直接设右端点为nn）
  2. 注意右端点和nn 取个minmin，因为 > n 没有贡献了。

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
int n, k, l, r;
LL ans;
int main() {
    scanf("%d%d", &n, &k);
    ans = (LL)n * k;
    for (l = 1; l <= n; l = r + 1) {
        if(k / l == 0) break;
        r = min(k / (k / l), n);
        ans -= (LL)(k / l) * (l + r) * (r - l + 1) / 2;
    }
    printf("%lld\n", ans);
    return 0;
}

最大公约数（gcd）

1
2
3
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

时间复杂度Θ(log⁡(a+b))\Theta(\log (a+b))。

VJwin6G - GCD Table

题意 给出抹去表头、内容乱顺序排列的最大公约数表，还原表头。

思路 举个栗子，

1
2
3
4
5
\ 2 3 3 6
2 2 1 1 2
3 1 3 3 3
3 1 3 3 3
6 2 3 3 6

输入的可能是这么一串数（当然它是随机排列的）：

1
1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 6

先用两个数组把它存起来，即

1
2
num[]={1,2,3,6};                         // 存数（排序后）
mp[1]=4, mp[2]=3, mp[3]=8, mp[6]=1;     // 记次数

由于给的这一串数一定包含表头本身，所以最大数和第二大的数都包含在其中（用反证法不难证明），本例中，6 和 3 一定是所求，记录答案，而且这两个数已经用过一次了，从 mp[] 数组中删去，现在是

1
2
3
num[]={1,2,3,6};
mp[1]=4, mp[2]=3, mp[3]=7, mp[6]=0;        // 删去了一个3和一个6
ans[]={6,3};

既然找到了 6 和 3，那它们的最大公约数也可以从表中删去，而且根据对称性，删两个，现在是

1
2
3
num[]={1,2,3};
mp[1]=4, mp[2]=3, mp[3]=5, mp[6]=0;        // 删去了两个gcd(3,6)=3
ans[]={6,3};

现在数组中的最大数是 3 了（6 的次数为 0，就当它不存在了），所以这个 3 也是结果之一，再删除它和已知两个数的最大公约数，现在是

1
2
3
num[]={1,2};
mp[1]=4, mp[2]=3, mp[3]=0, mp[6]=0;        // 删去了3,两个gcd(3,3)=3,两个gcd(3,6)=3
ans[]={6,3,3};

进而，

1
2
3
num[]={};
mp[1]=0, mp[2]=0, mp[3]=0, mp[6]=0;        // 删去了2,两个gcd(2,3)=1,两个gcd(2,3)=1,两个gcd(2,6)=2
ans[]={6,3,3,2};

至此，num[] 数组为空，删数完毕，结果便已经得到。

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
void eachT() {
    int n;
    cin >> n;

    map<int, ll> cnt;
    vector<int> num, ans;
    for (int i = 1; i <= n * n; i++) {
        int x;
        cin >> x;
        if (!cnt.count(x)) num.push_back(x);       // 存数 num[]={2,1,3,6}
        cnt[x]++;                                  // 记次数 cnt[1]=4, cnt[2]=3, cnt[3]=8, cnt[6]=1
    }
    sort(num.begin(), num.end());                  // num[]={1,2,3,6}

    while (num.size() > 0 && ans.size() < n) {
        while (!cnt[num.back()]) num.pop_back();   // 防止空数据，如cnt[4],cnt[5]一槪跳过
        ans.push_back(num.back());                 // 从最大开始记录ans[1]=num[6]
        --cnt[num.back()];                         // 删掉这个最大值ans[1]
        for (int j = 0; j < ans.size() - 1; ++j) {    // 现在有outcnt=1个已知的数
            cnt[gcd(num.back(), ans[j])] -= 2;     // 删掉与其它已知数的gcd，对称性删两个
        }
    }

    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
}

评注 核心在于删数的方法：最大的两个数一定是所求，删第一个数不用考虑附属的删谁，因为这时可以确定第二个数，之后每次删数时直接删与其它已知数的gcd⁡\gcd 就行。

VJwin6B - gcd.

题意 求gcd⁡(⌊lx⌋,⌊l+1x⌋,⋯ ,⌊rx⌋)\displaystyle\gcd(\lfloor \frac{l}{x}\rfloor,\lfloor \frac{l+1}{x}\rfloor,\cdots,\lfloor \frac{r}{x}\rfloor)。

思路 逐项算…… 然后TLE\mathbf{TLE}……

优化，只需算gcd⁡(⌊lx⌋,⌊lx⌋+1,⋯ ,⌊rx⌋)\displaystyle\gcd(\lfloor \frac{l}{x}\rfloor,\lfloor \frac{l}{x}\rfloor+1,\cdots,\lfloor \frac{r}{x}\rfloor)，项数减少了很多，但依然TLE\mathbf{TLE}……

继续优化，如果算到某个gcd⁡=1\gcd=1，就跳出，这样AC\rm AC 了。

评注 事实上除非⌊lx⌋=⌊rx⌋\displaystyle\lfloor \frac{l}{x}\rfloor=\lfloor \frac{r}{x}\rfloor，结果都是11，因为相邻两个自然数的gcd⁡=1\gcd=1，这也是没有TLE\rm TLE 的原因。

VJwin6C - GCD LCM

题意 给出gcd⁡(a,b)\gcd(a,b) 和lcm(a,b)\rm lcm(a,b)，找出一组(a,b)(a,b)。

思路 如果gcd⁡(a,b)∤lcm(a,b)\gcd(a,b)\nmid\rm lcm(a,b)，那么(a,b)(a,b) 不存在，如果存在，取这两个数本身，即a=gcd⁡(a,b), b=lcm(a,b)a=\gcd(a,b),~b={\rm lcm}(a,b) 即可。

VJwin13D - 小道消息

题意 有nn 个数2,3,…,n+12,3,\dots,n+1，零时刻将kk 涂色，每时刻对于每个有颜色的数ii，若(i,j)=1(i,j)=1，则将jj 涂色，在tt 时刻所有数都有颜色，求tt。

思路 注意到，每一时刻，奇数能传染所有偶数，偶数能传染所有奇数，因此t⩽2t\leqslant2。能否k=1k=1 呢？只要kk 与其它所有数互素即可。我们考虑t=2t=2 的情形，即∃j, s.t. (k,j)≠1\exists j,~\text{s.t. }(k,j)\ne1：

  • kk 为合数：设k=pk0k=pk_0，取j=pj=p，则(k,j)=p>1(k,j)=p>1；
  • 数列中存在2k2k，这等价于n⩾2kn\geqslant 2k。
1
int ans = (!isPrime(k + 1)) || n >= 2 * k + 1) ? 2 : 1;

评注 给出暴力代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ans = 0;
a[k] = aa[k] = 1;
while (!check()) {
    ans++;
    for (int i = 1; i <= n; i++) {
        if (a[i]) {
            for (int j = 1; j <= n; j++)
                if (gcd(i + 1, j + 1) == 1) aa[j] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
        a[i] = aa[i];
}
printf("%d\n", ans);

评注二

Bertrand-Chebyshev∀n>3, ∃ p, s.t. n<p<2n−2,∀n>1, ∃ p, s.t. n<p<2n.Generation1∀n>1, ∄ m,r>1, s.t. Ann=mr.Generation2∀n>0, ∄ m,r>1, s.t. C2nn=mr.\begin{array}{rl} \text{Bertrand-Chebyshev}\quad &\forall n>3,~\exists~ p,\text{ s.t. }n<p<2n-2, \\ &\forall n>1,~\exists~ p,\text{ s.t. }n<p<2n. \\ \text{Generation1}\quad &\forall n>1,~\nexists~ m,r>1,\text{ s.t. }A_n^n=m^r. \\ \text{Generation2}\quad &\forall n>0,~\nexists~ m,r>1,\text{ s.t. }C_{2n}^n=m^r. \end{array}

VJwin15B - 添加括号III（贪心）

题意 给出一个表达式，形如a0/a1/a2/a3/.../ana_{0}/a_{1}/a_{2}/a_{3}/.../a_{n}，问是否可以通过添加一些括号改变运算顺序使其成为一个整数。

思路 添加括号为a0/(a1/a2/a3/.../an)a_{0}/\big(a_{1}/a_{2}/a_{3}/.../a_{n}\big)，如果此时不能为整数，那么其它情形也不可能。

问题转化为判断a0a2a3…an mod a1=0a_0a_2a_3\dots a_n\bmod a_1=0。

实际判断[a0,a2,a3,...,an] mod a1=0[a_0, a_2, a_3, ..., a_n]\bmod a_1=0 即可。前面那一大坨没有a1a_1 的约数就寄了，可以边算边除，只保留和a1a_1 有公共约数的那一部分，也即最大公约数。

具体地说，对a1a_1 和aia_i，保留最大公约数，先变为a1a_1 和(a1,ai)(a_1,a_i)。然后来了aja_j，变为a1a_1 和(a1,ai)×(a1,aj)(a_1,a_i)\times(a_1,a_j)，最终要判断(a1,ai)×(a1,aj)×… mod a1(a_1,a_i)\times(a_1,a_j)\times\dots\bmod a_1
等价于gcd⁡(a1,aj)×… mod a1/gcd⁡(a1,ai)\gcd(a_1,a_j)\times\dots \bmod a_1/\gcd(a_1,a_i)。这时我们发现每次将a1a_1 变为(a1,ai)(a_1,a_i) 就足够了，最终是1 mod a1′1\bmod a_1'，只需判断a1′=1a_1'=1。

1
2
3
4
5
6
7
scanf("%d %d %d", &n, &x, &a);
a /= gcd(a, x);
for (ll i = 2; i < n; i++) {
    scanf("%lld", &x);
    a /= gcd(a, x);
}
printf("%s\n", a == 1 ? "Yes" : "No");

2024 牛客多校 4H - Yet Another Origami Problem（思维）

题意 给两种操作：排序数组后在值域上翻折一个前缀或翻折一个后缀，问任意次操作能做到的最小极差。

思路 排序去重后，答案为gcd⁡(ai+1−ai)\gcd(a_{i+1}-a_{i})。

1
2
3
4
5
6
7
8
9
10
11
12
13
void eachT() {
    int n = read();
    vector<ll> a(n);
    for (auto& i : a) i = read();
    sort(a.begin(), a.end());

    ll d = 0;
    for (int i = 1; i < n; i++) {
        d = gcd(d, a[i] - a[i - 1]);
    }

    printf("%lld\n", d);
}

2024 牛客多校 8A - Haitang and Game（思维）

[[…/contests/2024牛客多校/2024-08-08：2024牛客暑期多校训练营8|2024-08-08：2024牛客暑期多校训练营8]]

题意 给定一个集合SS。dXqwq 和 Haitang 轮流在集合中选择两个数，并将它们的最大公约数插入集合中，集合中元素不可相同。不可操作者败，求胜者。数据范围：1⩽n⩽105, 1⩽ai⩽1051 \leqslant n \leqslant 10^{5},\ 1 \leqslant a_{i} \leqslant 10^{5}，保证aia_{i} 严格单调递增。

思路 如果新插入的数的个数为奇数，dXqwq 胜，否则 Haitang 胜。我们推算最终集合。要判断最终集合中是否有dd，只需判断所有dd 的倍数的最大公约数是否是dd。枚举dd。时间复杂度为调和级数Θ(nlog⁡n)\Theta(n\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
void eachT() {
    int n = read();

    vector<int> mp(n + 1);
    for (int i = 1; i <= n; i++) {
        int x = read();
        mp[x] += 1;
    }

    int res = -n;

    for (int i = 1; i < N; i++) {
        int d = 0;
        for (int j = i; j < N; j += i) {
            if (mp[j]) {
                d = gcd(d, j);
            }
        }

        res += d == i;
    }

    printf("%s\n", res & 1 ? "dXqwq" : "Haitang");
}

2024 牛客多校 10F. Collinear Exception

[[…/contests/2024牛客多校/2024-08-15：2024牛客暑期多校训练营10|2024-08-15：2024牛客暑期多校训练营10]]

给定一个二维平面点的排列，从前到后依次插入一个初始为空集合。如果插入后会导致三点共线，那么会跳过这次插入。输出每次插入是否成功。

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
int vis[N][N];
int res[N * N];
pii S[N * N];

void eachT() {
    int n = read();

    int cnt = 0;
    for (int i = 0; i < n * n; i++) {
        int x = read(), y = read();

        if (vis[x][y]) continue;
        vis[x][y] += 1;
        res[i] = 1;

        for (int j = 0; j < cnt; ++j) {
            auto& [x0, y0] = S[j];
            int dx = x - x0, dy = y - y0, x1, y1;
            int d = gcd(dx, dy);
            dx /= d, dy /= d;

            x1 = x0 + dx, y1 = y0 + dy;
            while (x1 <= n && y1 <= n && x1 >= 1 && y1 >= 1) {
                vis[x1][y1] += 1;
                x1 += dx, y1 += dy;
            }

            x1 = x0 - dx, y1 = y0 - dy;
            while (x1 <= n && y1 <= n && x1 >= 1 && y1 >= 1) {
                vis[x1][y1] += 1;
                x1 -= dx, y1 -= dy;
            }
        }

        S[cnt++] = { x, y };
    }

    for (int i = 0; i < n * n; i++) {
        printf("%d", res[i]);
    }
}

互质与欧拉函数

1∼N1\sim N 中与NN 互质的个数被称为欧拉函数，记为φ(N)\varphi(N)
若在算术基本定理中，N=p1c1p2c2…pmcmN = p_{1}^{c_{1}}p_{2}^{c_{2}}\dots p_{m}^{c_{m}} ，则 :

\varphi(N) = N*\cfrac{(p_{1}-1)}{p_{1}}*\cfrac{(p_{2}-1)}{p_{2}}*\dots*\cfrac{(p_{m}-1)}{p_{m}} $$ 性质： 1. $\forall n>1,1\sim n$ 中与 $n$ 互质的数的和为 $\cfrac{n*\varphi(n)}{2}$ 2. 若 $a,b$ 互质，则 $\varphi(ab)=\varphi(a)\varphi(b)$

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
int m;
int p[N];
int c[N];
void divide(int n)
{
    m = 0;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            p[++m] = i;
            c[m] = 0;
            while (n % i == 0)
                c[m]++, n /= i;
        }
    }
    if (n > 1) // n是质数
    {
        p[++m] = n, c[m] = 1;
    }
}

void eachT()
{
    int n = read();
    divide(n);
    ll ans = n;
    for (int i = 1; i <= m; i++)
    {
        ans = ans * (p[i] - 1) / p[i];  // 注意这里不能缩写
    }
    cout << ans << endl;
}

时间复杂度：$O(\sqrt{ N })$ 若加上素数筛，时间复杂度的常数会更小 # 暴力枚举 lcm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return 1ll * a * b / gcd(a, b); }

constexpr int N = 1e5 + 8;
vector<int> divisor[N];
vector<pii> pairs[N];
void initlcm() {
    for (int i = 1; i < N; i++) {
        for (int L = i; L < N; L += i)
            divisor[L].emplace_back(i);
    }
    for (int i = 1; i < N; i++) {
        for (int L = i; L < N; L += i) {
            for (int& j : divisor[L]) {
                if (i >= j and lcm(i, j) == L)
                    pairs[L].emplace_back(i, j);
            }
        }
    }
}
# 同余 ## 2024 牛客多校 3B - Crash Test [[../contests/2024-07-23：2024牛客暑期多校训练营3|2024-07-23：2024牛客暑期多校训练营3]] **题意** 给定 $n$ 类操作，每次可将 $x$ 更新为 $\left|x-a_i\right|$，求从 $D$ 开始可得到的最小值。 数据范围：$n \leqslant 100,\ 1 \leqslant a_i, D \leqslant 10^{18}$。 **思路** 直观感受为裴蜀定理，设 $d=\gcd a,\ r=D \bmod d$，答案为 $\min\lbrace r,d-r \rbrace$。 **解** 当 $n=2$ 时，不妨 $a_1<a_2$。 令 $g=\operatorname{gcd}\left(a_1, a_2\right)$，我们将证明能生成如下元素：

\set{0 \leq x \leq a_2 \mid(D-x) \bmod g=0 \lor (D+x) \bmod g=0}

1. 通过操作 $x \leftarrow\left|x-a_1\right|$, 我们可将数 $x$ 更新为 $a_1-x \bmod a_1$ 2. 通过操作 $x \leftarrow\left|x-a_2\right|$, 我们可将数 $x$ 更新为 $a_2-\left(a_1-x\right.\left.\bmod a_1\right)=a_2-a_1+x \bmod a_1$ 3. 通过操作 $x \leftarrow\left|x-a_1\right|$, 我们可将数 $x$ 更新为 $\left(x+a_2\right) \bmod a_1$因此, 我们能够生成 $a_1$ 内（容易推广到 $a_2$ 内）所有模 $g$ 与 $D$ 同余的数。同理，我们也能够生成 $a_1$ 内所有模 $g$ 与 $-D$ 同余的数。 数学归纳法可推广至任意的 $n$ （只需取 $g=\operatorname{gcd}\left(a_1, a_2, \ldots, a_n\right)$ 即可）。

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
#include <cstdio>
#include <algorithm>
using ll = long long;
const int N = 1e5 + 10;
inline ll read() {
    ll S = 0, C = 0; char Y = getchar();
    while (Y > 57 || Y < 48) C |= Y == 45, Y = getchar();
    while (Y <= 57 && Y >= 48) S = (S << 3) + (S << 1) + Y - 48, Y = getchar();
    return C ? -S : S;
}

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

int main() {
    int n = read();
    ll D = read();

    ll d = read();
    for (int i = 2; i <= n; i++) {
        ll x = read();
        d = gcd(d, read());
    }

    ll left = D % d;
    printf("%lld\n", min(left, d - left));

    return 0;
}
<div STYLE="page-break-after: always;"></div> ## CF1994D. Funny Game **题意** 给定一个只有点没有边的图，点权为 $a_{i}$，进行 $n - 1$ 次操作，第 $i~(1 \leqslant i \leqslant n-1)$ 次操作定义为： - 任意选择 $2$ 个点 $u,v$，满足 $|a_u - a_v|$ 被 $i$ 整除，在 $u$ 和 $v$ 间连一条边． 判断能否将图连为一棵树，如果能，给出操作方案． **思路** 为什么选择倒着连？第 $x$ 次操作的时候有 $x+1$ 个连通块，每个连通块即使选一个数出来也一定存在两个数同余 $x$。
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
#include <cstdio>
#include <map>
#include <vector>
using ll = long long;
inline ll read() {
    ll S = 0, C = 0; char Y = getchar();
    while (Y > 57 || Y < 48) C |= Y == 45, Y = getchar();
    while (Y <= 57 && Y >= 48) S = (S << 3) + (S << 1) + Y - 48, Y = getchar();
    return C ? -S : S;
}

// 并查集
const int N = 2e3 + 8;
int fa[N];
inline void init() { for (int i = 0; i < N; i++) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void uno(int x, int y) { fa[find(x)] = find(y); }
inline bool same(int x, int y) { return find(x) == find(y); }

void eachT() {
    int n = read();
    vector<int> a(n);
    for (auto& x : a) x = read();

    init();
    vector<pair<int, int> > ans;
    for (int k = n - 1; k >= 1; k--) {
        vector<int> mp(k, -1);
        for (int i = 0; i < n; i++) {
            auto& j = mp[a[i] % k];
            if (j != -1 && !same(i, j)) {
                uno(i, j);
                ans.push_back({ i, j });
                break;
            }
            else {
                j = i;
            }
        }
    }

    printf("YES\n");
    for (int i = ans.size() - 1; i >= 0; i--) {
        auto& [u, v] = ans[i];
        printf("%d %d\n", u + 1, v + 1);
    }
}

int main() {
    for (int T = read(); T--; eachT());
    return 0;
}
# 数论倒数 ## [VJwin13I - 模意义下的乘法逆元 2](https://www.luogu.com.cn/problem/P5431) **题意** 求 $\displaystyle\sum_{i=1}^{n}\frac{k^i}{a_i}\bmod p$。 **思路** 为减小时间复杂度，我们只能计算一次数论倒数。 **方法一** 边计算边通分。设前 $i-1$ 项的和为 $\displaystyle\frac{f_1}{f_2}$，则前 $i$ 项的和为 $\displaystyle\frac{f_1}{f_2}+\frac{k^i}{a_i}=\frac{a_if_1+k^if_2}{a_if_2}$，故令 $f_1:=a_if_1+k^if_2,~f_2:=a_if_2$，最终的结果是 $f_1\cdot f_2^{-1}\bmod p$，只需计算一次数论倒数，时间复杂度 $\Theta(n+\log p)$。
1
2
3
4
5
6
7
8
9
read(n), read(p), read(k);
ll pow = 1, frac1 = 0, frac2 = 1; // k的幂 分子 分母
for (int i = 1; i <= n; i++) {
    read(x);
    pow = (pow * k) % p;
    frac1 = (frac1 * x + frac2 * pow) % p;
    frac2 = (frac2 * x % p);
}
print(frac1 * Inv(frac2, p) % p);
**方法二** 直接通分，结果为 $\displaystyle\frac{\sum_{i=1}^{n}k^ia_1\dots a_{i-1}a_{i+1}\dots a_n}{a_1a_2\dots a_n}$，对于分母，可以预处理 $\{a_i\}$ 的前缀积和后缀积，时间复杂度 $\Theta(3n+\log p)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
read(n), read(p), read(k);
ll ans = 0, pow = 1;
fst[0] = lst[n + 1] = 1;
for (int i = 1; i <= n; i++) {
    read(a[i]);
    fst[i] = fst[i - 1] * a[i] % p;
}
for (int i = n; i; --i)
    lst[i] = lst[i + 1] * a[i] % p;
for (int i = 1; i <= n; i++) {
    pow = (pow * k) % p;
    ans = (ans + pow * fst[i - 1] % p * lst[i + 1]) % p;
}
print(ans * inv(fst[n], p) % p);