Znzryb's Blog

完全理解欧拉函数的计算和欧拉定理（使用线性筛求解）（使用试除法求解）

Posted on 2026-03-13 Edited on 2026-04-06

【G09 筛法求欧拉函数】 https://www.bilibili.com/video/BV1VP411p7Bs/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-B. Be knocked off 被抠的键盘（构造题，我们需要思考的就是，我们有没有办法化繁为简？）（一般这种构造题目，无解情况不会特别多）

这个对的原因是，显然，和 $p^k$ 不互素的只有 p 的倍数，因此就是 $\phi(p^k)=p^k-(p 的倍数的数量)$ 。

$1 \cdot p,\quad 2 \cdot p,\quad 3 \cdot p,\quad 4 \cdot p,\quad 5 \cdot p,\quad 6 \cdot p,\quad \ldots,\quad (p^{k-1} - 2) \cdot p,\quad (p^{k-1} - 1) \cdot p,\quad p^{k-1} \cdot p$

p 的倍数的系数可以从 $1$ 一直取到 $p^{k-1}$ ，所以一共 $p^{k-1}$ 个。最后一项 $p^{k-1} \cdot p = p^k$ ，刚好是上界。

因此 $\phi(p^k)=p^k-p^{k-1}$ 。

有了上面的这个公式，就不难推出如下式子。

其实这个式子，形象化的理解，就是不断的把 n 里面，p 的倍数（p 都是质数，因此倍数与倍数之间互不干扰）给筛掉。

当然，如果进行朴素相减，会出现问题。

不过，那为什么乘积不会出现这个问题呢？答案就是容斥原理。

这就是乘法的容斥原理。因为乘法的本质就是在枚举子集，只要一个负号，让其符合这个容斥原理的奇减偶加特性即可。


/*
 * 试除法求一个数的欧拉函数（也就是求 [1,n] 内与其互素的数的个数）
 * 2026-03-13: AC https://codeforces.com/gym/106380/submission/366492238
 */
long long euler_phi(long long n) {
    long long res = n;
    // p 从 2 开始，逐个递增，试到 sqrt(n) 为止
    for (long long p = 2; p * p <= n; p++) {
        // 如果 p 能整除 n，那么 p 一定是质数。
        // 为什么？因为如果 p 是合数，比如 p = 6 = 2 × 3，
        // 那么在 p=2 和 p=3 的时候，n 中的 2 和 3 已经被除干净了，
        // 此时 n 不可能被 6 整除，所以 n % 6 != 0，这个 if 进不来。
        // 因此能进到这个 if 里的 p，一定是质因子。
        if (n % p == 0) {
            // 发现质因子 p，对 res 乘上 (1 - 1/p) 这个因子
            // 即 res = res / p * (p - 1)
            res = res / p * (p - 1);
            // 把 n 中所有的 p 除干净
            // 这样后续更大的 p 的倍数就不可能再整除 n 了
            while (n % p == 0) n /= p;
        }
    }
    // 循环结束后，如果 n > 1，说明 n 还剩一个大于 sqrt(原始n) 的质因子
    // （一个数最多只有一个大于 sqrt 的质因子）
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

那么都有上面的，非常符合直觉的计算公式了，我们也是非常 easy 的能够证明这个东西。

只要把这个东西全部列出来，就非常容易的可以证明。当然，要求 n，m 互素，否则他们的质数项一定会有交集，那么就失效了，积性函数性质。

这是 Euler 定理（欧拉定理）。

对于任意正整数 $m$ 和整数 $a$ ，若 $\gcd(a, m) = 1$ ，则

a^{\varphi(m)} \equiv 1 \pmod{m}

证明：考虑模 $m$ 的缩系（即 $1$ 到 $m$ 中所有与 $m$ 互素的数构成的集合 $S$ ，共 $\varphi(m)$ 个元素）。当 $\gcd(a, m) = 1$ 时，把 $S$ 中每个元素都乘以 $a$ ，得到的集合模 $m$ 后恰好还是 $S$ （因为乘以 $a$ 是模 $m$ 缩系上的一个双射）。于是把所有元素的乘积写出来：

\prod_{x \in S} (ax) \equiv \prod_{x \in S} x \pmod{m}

左边提出 $a$ ：

a^{\varphi(m)} \times \prod_{x \in S} x \equiv \prod_{x \in S} x \pmod{m}

因为 $\prod_{x \in S} x$ 与 $m$ 互素（因为 $S$ 中每个元素都与 $m$ 互素，这里我们用到了 S 的定义）（说白了，只要是除数和 m 互素，就有逆元，就可以除），可以两边消掉，就得到 $a^{\varphi(m)} \equiv 1 \pmod{m}$ 。

它的特殊情况是 Fermat 小定理：当 $m = p$ 为素数时， $\varphi(p) = p - 1$ ，即 $a^{p-1} \equiv 1 \pmod{p}$ 。

完全理解线性筛

Posted on 2026-03-13 Edited on 2026-04-06

线性筛

线性筛的作用就是为了保证每个合数都只被其【最小的】那个质因数标记一次。

这下面👇讲的比较一般啊。

线性筛只有可能标记一个数字一次。

这个讲的有点复杂了，最后是关键，就是每个数只会以唯一方式被标记。

m=\frac{n}{p_1}=p_{1}^{m_1-1}\times p_{2}^{m_2}\times p_{3}^{m_3} \times \cdots \times p_{k}^{m_k}

n 只会在遍历到 m 时被标记。

假设这个n，在遍历到 m 之前就被标记，假设该数字是 m‘，但是 $m’\times \text{minp}[m']=n$ 是必须满足的条件，if(p==minp[i]) break; ，m‘ 只会标记到这个最小素因子*自身，因此 m’ 想标记 n，当且仅当 $m’\times \text{minp}[m']=n$ 。显然，m‘=m，得证。

https://qoj.ac/submission/995868

https://cp-algorithms.com/algebra/prime-sieve-linear.html

//  minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
vector<ll> minp,primes;
void sieve(ll n){
    minp.assign(n+5,0);
    // minp[1]=1;  // 加了这句话可能把 1 误判成素数，要小心
    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;
            // 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
            // i * p_next = (p * k) * p_next 最小的应该是p
            if(p==minp[i]){
                break;
            }
        }
    }
}

使用线性筛的minp分解素因数更快，效率更高。

vector<ll> prs;
for(int j=W[i];j>1;j/=minp[j]){		// 素因数分解
	ll p=minp[j];
	prs.pb(p);
}
sort(all(prs));
prs.resize(unique(all(prs))-prs.begin());

The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-B. Be knocked off 被抠的键盘（构造题，我们需要思考的就是，我们有没有办法化繁为简？）（一般这种构造题目，无解情况不会特别多）

Posted on 2026-03-13 Edited on 2026-04-06

题目大意

题目描述
你有一个包含数字 $0$ 到 $9$ 的键盘。给定一个正整数 $m$ ，你的目标是使用键盘打出一个正整数，使其为 $m$ 的倍数。

但是，键盘上有 $k$ 个正整数按键损坏了（数字 $0$ 的按键一定完好，只有 $1$ 到 $9$ 中的部分按键可能损坏）。你只能使用剩下的完好按键来打出这个数字。

输入格式
第一行包含一个整数 $T$ （ $1 \le T \le 5 \times 10^4$ ），表示测试数据的组数。

对于每组测试数据：
第一行包含两个整数 $m$ 和 $k$ （ $1 \le m \le 10^7$ ， $0 \le k \le 9$ ），表示目标数字必须是 $m$ 的倍数，且有 $k$ 个按键损坏。

用其他剩余按键，敲出 m 的倍数。

第二行包含 $k$ 个互不相同的整数 $p_i$ （ $1 \le p_i \le 9$ ），具体表示哪些数字按键被损坏。

输出格式
对于每组测试数据：
如果存在合法的构造方案，请以“连续按下某数字 $a$ 共 $b$ 次”的操作序列形式输出：
第一行输出一个整数 $n$ （ $1 \le n \le 100$ ），表示操作的数量。
接下来 $n$ 行，每行输出两个整数 $a$ 和 $b$ （ $0 \le a \le 9$ ， $1 \le b \le 10^{18}$ ），表示按下数字 $a$ 共 $b$ 次。

如果不存在任何合法的方案，仅输出一行 -1。

样例

输入:
2
37 7
2 3 5 6 7 8 9
7 9
1 2 3 4 5 6 7 8 9

输出:
2
1 3
0 1
-1

样例解释
对于第一组样例，给出的操作为：按下数字 $1$ 共 $3$ 次，然后按下数字 $3$ 共 $1$ 次。这样按出来的正整数是 $1110$ 。由于 $1110 = 37 \times 30$ ，它是 $37$ 的倍数，并且只使用了未损坏的按键 $1$ 和 $0$ ，符合题目要求。

对于第二组样例，数字 $1$ 到 $9$ 的按键全部损坏，唯一能打出的是由数字 $0$ 组成的数（值为 $0$ ）。但题目要求打出的必须是一个正整数，因此无法完成任务，输出 -1。

思路讲解

欧拉定理的介绍以及证明

这是 Euler 定理（欧拉定理）。
内容很简洁：对于任意正整数 $m$ 和整数 $a$ ，若 $\gcd(a, m) = 1$ ，则

a^{\varphi(m)} \equiv 1 \pmod{m}

其中 $\varphi(m)$ 是欧拉函数，表示 $1$ 到 $m$ 中与 $m$ 互素的正整数个数。
图中的结论就是把 $a = 10$ 代入：因为已经去掉了 $m$ 中 $2$ 和 $5$ 的因子，保证了 $\gcd(10, m) = 1$ ，所以直接套用 Euler 定理得到 $10^{\varphi(m)} \equiv 1 \pmod{m}$ 。
直觉上为什么成立：考虑模 $m$ 的缩系（即 $1$ 到 $m$ 中所有与 $m$ 互素的数构成的集合 $S$ ，共 $\varphi(m)$ 个元素）。当 $\gcd(a, m) = 1$ 时，把 $S$ 中每个元素都乘以 $a$ ，得到的集合模 $m$ 后恰好还是 $S$ （因为乘以 $a$ 是模 $m$ 缩系上的一个双射）。于是把所有元素的乘积写出来：

\prod_{x \in S} (ax) \equiv \prod_{x \in S} x \pmod{m}

左边提出 $a$ ：

a^{\varphi(m)} \times \prod_{x \in S} x \equiv \prod_{x \in S} x \pmod{m}

因为 $\prod_{x \in S} x$ 与 $m$ 互素（ $S$ 中每个元素都与 $m$ 互素）（说白了，只要是除数和 m 互素，就有逆元，就可以除），可以两边消掉，就得到 $a^{\varphi(m)} \equiv 1 \pmod{m}$ 。
它的特殊情况是 Fermat 小定理：当 $m = p$ 为素数时， $\varphi(p) = p - 1$ ，即 $a^{p-1} \equiv 1 \pmod{p}$ 。

呃，首先我们还是一步一步来吧，就是首先，我们可以想到，就是 m 当中的这个因数还是越少越好嘛，想办法先消掉一些。

下面这一步也是比较自然的，因为注意到，0 是永远都在的。

我们可以把这个 m 当中的因数 2,5 给除掉（因为如果原数字不满足，就加 0 即可），得到的新 m 和这个 10 互质（反正应该就是想办法让原数和 10 互质，可以通过不断除以 10，记录一下除 10 的这个个数，最后 +0 即可）。

然后，就可以想到欧拉定理（其实我们的构造目标就是一个同余式，我们得到的任何东西，也要想办法化为同余式）：

这是 Euler 定理（欧拉定理）。

对于任意正整数 $m$ 和整数 $a$ ，若 $\gcd(a, m) = 1$ ，则

a^{\varphi(m)} \equiv 1 \pmod{m}

不难得出如下结论：

我们现在是构出来了，但是万一 9 被扣了我们不就炸了？

我们发现，只要我们能够勾出来一个全 1 的，我们能够非常自然的勾出全 d 的。

这个最后一步，也挺难的，反正我确实不大能够推出来。使用了变量直接代换的这个技巧，把一个 9 带到了这个整除符号的两边。

ll cnt2=0;
while (M%2==0) {
    M/=2;
    cnt2++;
}
ll cnt5=0;
while (M%5==0) {
    M/=5;
    cnt5++;
}
ll phi=euler_phi(M);
ll cnt0=max(cnt2,cnt5);
if (cnt0==0) {
    cout<<1<<"\n";
}else {
    cout<<2<<"\n";
}
cout<<*keys.rbegin()<<" "<<9*phi<<"\n";
if (cnt0!=0) {
    cout<<0<<" "<<cnt0<<"\n";
}

AC代码

AC
https://codeforces.com/gym/106380/submission/366492238

源代码

/**
 * Problem: B. Be knocked off
 * Contest: The 6th Liaoning Provincial Collegiate Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106380/problem/B
 * Created: 2026-03-13 10:57:19
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
long long euler_phi(long long n) {
    long long res = n;
    // p 从 2 开始，逐个递增，试到 sqrt(n) 为止
    for (long long p = 2; p * p <= n; p++) {
        // 如果 p 能整除 n，那么 p 一定是质数。
        // 为什么？因为如果 p 是合数，比如 p = 6 = 2 × 3，
        // 那么在 p=2 和 p=3 的时候，n 中的 2 和 3 已经被除干净了，
        // 此时 n 不可能被 6 整除，所以 n % 6 != 0，这个 if 进不来。
        // 因此能进到这个 if 里的 p，一定是质因子。
        if (n % p == 0) {
            // 发现质因子 p，对 res 乘上 (1 - 1/p) 这个因子
            // 即 res = res / p * (p - 1)
            res = res / p * (p - 1);
            // 把 n 中所有的 p 除干净
            // 这样后续更大的 p 的倍数就不可能再整除 n 了
            while (n % p == 0) n /= p;
        }
    }
    // 循环结束后，如果 n > 1，说明 n 还剩一个大于 sqrt(原始n) 的质因子
    // （一个数最多只有一个大于 sqrt 的质因子）
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}
void Solve() {
    ll M,N;
    cin >> M >> N;
    set<ll> keys={0,1,2,3,4,5,6,7,8,9};
    for (int i=1;i<=N;++i) {
        ll a;
        cin>>a;
        keys.erase(a);
    }
    if (SZ(keys)==1) {
        cout<<-1<<"\n";
        return;
    }
    ll cnt2=0;
    while (M%2==0) {
        M/=2;
        cnt2++;
    }
    ll cnt5=0;
    while (M%5==0) {
        M/=5;
        cnt5++;
    }
    ll phi=euler_phi(M);
    ll cnt0=max(cnt2,cnt5);
    if (cnt0==0) {
        cout<<1<<"\n";
    }else {
        cout<<2<<"\n";
    }
    cout<<*keys.rbegin()<<" "<<9*phi<<"\n";
    if (cnt0!=0) {
        cout<<0<<" "<<cnt0<<"\n";
    }

#ifdef LOCAL

#endif
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106380/submission/366492238

*/

心路历程（WA，TLE，MLE……） $37$ $1$ $1 \le b \le 10^{18}$

The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-赛后 vp 总结

Posted on 2026-03-12 Edited on 2026-08-14

基本情况

乱打的，比较狗屎了。

心得感悟

感觉还是要做中国的省赛，感觉中国的题目和国外的题目还是风格有所不同吧。

题目 I take from the richer

就是这个排序一遍以后直接模拟。

不难发现，肯定是先选小的数，因为先选大的数，小的数就没法贡献了。

这种一定要小心这个加上一个负数，要用这个 max 0ll 去兜底。

https://codeforces.com/gym/106380/submission/366235168

源代码

/**
 * Problem: I. I take from the richer
 * Contest: The 6th Liaoning Provincial Collegiate Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106380/problem/I
 * Created: 2026-03-11 17:59:15
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (int i=0;i<N;++i) {
        cin>>A[i];
    }
    // for (int i=1;i<N;++i) {
    //     A[i]-=A[0];
    //     A[i]=max(A[i],0ll);
    // }
    // ll l=0,r=accumulate(A.begin()+1,A.end(),0ll);
    // auto check=[&](ll add) -> bool {
    //     for (int i=1;i<N;++i) {
    //
    //     }
    // };
    // while (l<r) {
    //     ll mid=l+r>>1;
    //     if (check(mid)) {
    //
    //     }else {
    //
    //     }
    // }
    // cout<<l+A[0]<<"\n";
    sort(A.begin()+1,A.end());
    ll ans=A[0];
    for (int i=1;i<N;++i) {
        ans+=max(0ll,(A[i]+1-ans)/2);
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106380/submission/366235168

*/

题目 Just reseat!

模拟题，不多说了。

https://codeforces.com/gym/106380/submission/366229614

源代码

/**
 * Problem: J. Just reseat!
 * Contest: The 6th Liaoning Provincial Collegiate Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106380/problem/J
 * Created: 2026-03-11 19:12:09
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
// struct J_id {
//     ll
// };
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<ll> > g(N+2);
    for (int i=1;i<=M;++i) {
        ll op;
        cin>>op;
        if (op==1) {
            ll exp,id;
            cin>>exp>>id;
            exp--;
            g[exp].push_back(id);
        }else {
            ll exp1,j1,exp2,j2;
            cin>>exp1>>j1>>exp2>>j2;
            exp1--;
            exp2--;
            j1--;
            j2--;
            swap(g[exp1][j1],g[exp2][j2]);
        }
    }
    for (int i=0;i<N;++i) {
        cout<<SZ(g[i])<<" ";
        for (int j=0;j<SZ(g[i]);++j) {
            cout<<g[i][j]<<" ";
        }
        cout<<"\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106380/submission/366229614

*/

题目 Do you play Ballance?

直接分类讨论。

vector<A_b_c> A(N+2);
vector<ll> cnt(10);
for (int i=1;i<=N;++i) {
    ll a,b,c;
    cin>>a>>b>>c;
    A[i]={a,b,c};
    if (A[i]==A_b_c{1,0,0}) {
        cnt[1]++;
    }else if (A[i]==A_b_c{0,1,0}) {
        cnt[2]++;
    }else if (A[i]==A_b_c{0,0,1}){
        cnt[3]++;
    }
}
if (cnt[1] && cnt[2] && cnt[3]) {
    cout<<3<<"\n";
    return;
}
for (int i=1;i<=N;++i) {
    if (A[i]==A_b_c{1,0,0}) {

    }else if (A[i]==A_b_c{0,1,0}) {

    }else if (A[i]==A_b_c{0,0,1}){

    }else {
        if (A[i].a && cnt[1]) {
            ++cnt[1];
        }else if (A[i].b && cnt[2]) {
            ++cnt[2];
        }else if (A[i].c && cnt[3]) {
            ++cnt[3];
        }else if (A[i]==A_b_c{1,1,0}) {
            ++cnt[4];
        }else if (A[i]==A_b_c{1,0,1}) {
            ++cnt[5];
        }else if (A[i]==A_b_c{0,1,1}) {
            ++cnt[6];
        }else if (A[i]==A_b_c{1,1,1}) {
            ++cnt[7];
        }
    }
}
ll ans1=ll(bool(cnt[1]))+ll(bool(cnt[2]))+ll(bool(cnt[3]));
ll ans2=ll(bool(cnt[4]))+ll(bool(cnt[5]))+ll(bool(cnt[6]));
ll ans=ans1;
if (ans1) {
    if (ans2) {
        ++ans;
    }
}else {
    if (ans2<=2) {
        ans=1;
    }else {
        ans=2;
    }
}
if (ans==0 && cnt[7]) {
    ++ans;
}
cout<<ans<<"\n";

https://codeforces.com/gym/106380/submission/366228036

源代码

/**
 * Problem: D. Do you play Ballance?
 * Contest: The 6th Liaoning Provincial Collegiate Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106380/problem/D
 * Created: 2026-03-11 18:32:54
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct A_b_c {
    ll a,b,c;
    auto operator<=>(const A_b_c&o) const = default;
};
void Solve() {
    ll N;
    cin >> N;
    vector<A_b_c> A(N+2);
    vector<ll> cnt(10);
    for (int i=1;i<=N;++i) {
        ll a,b,c;
        cin>>a>>b>>c;
        A[i]={a,b,c};
        if (A[i]==A_b_c{1,0,0}) {
            cnt[1]++;
        }else if (A[i]==A_b_c{0,1,0}) {
            cnt[2]++;
        }else if (A[i]==A_b_c{0,0,1}){
            cnt[3]++;
        }
    }
    if (cnt[1] && cnt[2] && cnt[3]) {
        cout<<3<<"\n";
        return;
    }
    for (int i=1;i<=N;++i) {
        if (A[i]==A_b_c{1,0,0}) {

        }else if (A[i]==A_b_c{0,1,0}) {

        }else if (A[i]==A_b_c{0,0,1}){

        }else {
            if (A[i].a && cnt[1]) {
                ++cnt[1];
            }else if (A[i].b && cnt[2]) {
                ++cnt[2];
            }else if (A[i].c && cnt[3]) {
                ++cnt[3];
            }else if (A[i]==A_b_c{1,1,0}) {
                ++cnt[4];
            }else if (A[i]==A_b_c{1,0,1}) {
                ++cnt[5];
            }else if (A[i]==A_b_c{0,1,1}) {
                ++cnt[6];
            }else if (A[i]==A_b_c{1,1,1}) {
                ++cnt[7];
            }
        }
    }
    ll ans1=ll(bool(cnt[1]))+ll(bool(cnt[2]))+ll(bool(cnt[3]));
    ll ans2=ll(bool(cnt[4]))+ll(bool(cnt[5]))+ll(bool(cnt[6]));
    ll ans=ans1;
    if (ans1) {
        if (ans2) {
            ++ans;
        }
    }else {
        if (ans2<=2) {
            ans=1;
        }else {
            ans=2;
        }
    }
    if (ans==0 && cnt[7]) {
        ++ans;
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106380/submission/366228036

*/

The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-M. Many CF Rounds vs Capoo 猫猫虫打 CF（这种有一个元素有两个值的这种东西，可以把他们看作是一条线段，画在这个数轴上面，兴许可以看出些什么，至少比干瞪眼好）

Posted on 2026-03-12 Edited on 2026-04-06

题目大意

题目描述
Capoo 的初始 rating 为 $x=0$ 。
现在有 $n$ 场比赛，对于第 $i$ 场比赛，它的难度为 $a_i$ ，隐藏分数为 $b_i$ 。每场比赛最多只能参加一次。
只有当当前 rating $x \le a_i$ 时，Capoo 才能参加第 $i$ 场比赛。参加完该场比赛后，Capoo 的 rating 将会更新为 $\max(b_i, x)$ 。
你可以自由安排参加这 $n$ 场比赛的顺序，求 Capoo 最多能参加多少场比赛。

输入格式
第一行包含一个整数 $n$ （ $1 \le n \le 10^6$ ）。
接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ （ $0 \le a_i, b_i \le 10^{18}$ ），分别表示第 $i$ 场比赛的难度和隐藏分数。

输出格式
输出一行一个整数，表示 Capoo 最多能参加的比赛场数。

样例

样例解释

注意，这个人比较喜欢挑战这个难题。
一种最多参加 $5$ 场比赛的合法顺序如下：

初始时 $x = 0$ 。
参加第 $7$ 场比赛（ $a_7=0, b_7=7$ ）：满足 $x \le a_7$ （ $0 \le 0$ ），参加后 $x$ 更新为 $\max(0, 7) = 7$ 。
参加第 $5$ 场比赛（ $a_5=18, b_5=3$ ）：满足 $x \le a_5$ （ $7 \le 18$ ），参加后 $x$ 更新为 $\max(7, 3) = 7$ 。
参加第 $6$ 场比赛（ $a_6=16, b_6=9$ ）：满足 $x \le a_6$ （ $7 \le 16$ ），参加后 $x$ 更新为 $\max(7, 9) = 9$ 。
参加第 $10$ 场比赛（ $a_{10}=15, b_{10}=17$ ）：满足 $x \le a_{10}$ （ $9 \le 15$ ），参加后 $x$ 更新为 $\max(9, 17) = 17$ 。
参加第 $1$ 场比赛（ $a_1=19, b_1=18$ ）：满足 $x \le a_1$ （ $17 \le 19$ ），参加后 $x$ 更新为 $\max(17, 18) = 18$ 。
总计参加了 $5$ 场比赛，可以证明这是最多能参加的比赛场数。

思路讲解

将所有比赛分成两组：

安全组 A： $b_i \le a_i$ 。参加后 $x \leftarrow \max(x, b_i) \le a_i$ ，也就是说参加这场比赛不会把 $x$ 抬到超过它自身的门槛 $a_i$ 。对后续的影响很温和。
危险组 B： $b_i > a_i$ 。参加后 $x$ 必然跳到 $b_i$ （因为 $b_i > a_i \ge x$ ），对后续影响大。

为什么这个分组有用？因为安全组内部，如果按 $a_i$ 升序排列，全部都能参加——每次参加后 $x \le a_i$ ，而下一场的 $a$ 更大，必然满足条件。所以安全组是"稳赚不赔"的。

下一步应该关注：安全组全做了，危险组怎么尽可能多地塞进来**？（把安全组给固定住）**

第三层：排序与交错——两组的最优合并策略

安全组按 $a_i$ 升序排。
危险组按 $b_i$ 升序排（参加后 $x$ 跳到 $b_i$ ，越小越好，留给后面的空间越大）。

一下的这个规则就是，在上面情况下，B 不会影响 A？（先不要去想 B 会不会生效）

关键的交错规则：在做每一个危险组比赛 $B_j$ （ $b$ 值为 $b_j$ ）之前，先把安全组中所有 $a_i < b_j$ 的比赛做完。

为什么？做完 $B_j$ 后 $x = b_j$ ，那些 $a < b_j$ 的安全组比赛就再也做不了了。提前做掉它们不会抬高 $x$ （因为安全组的 $b \le a < b_j$ ），不影响 $B_j$ 的可行性。

这样，安全组的比赛一场都不会浪费——它们总是在 $x$ 被抬高之前被消化掉。最终的答案就是：

\text{安全组全部} + \text{按上述交错策略能做的危险组数量}

不难想到，危险组按照这个 b 从小到大排比较好，

auto forward=[&]() -> bool {
    while (idx1<SZ(safeA) && idx2<SZ(dangerA) && safeA[idx1].a<dangerA[idx2].b) {
        cur_ability=max(cur_ability,safeA[idx1].b);
        ++idx1;
    }

    if (cur_ability<=dangerA[idx2].a) {
        cur_ability=max(cur_ability,dangerA[idx2].b);
        ++ans;
    }
    ++idx2;
    if (idx2<SZ(dangerA)) {
        return true;
    }
    return false;
};
while (forward()) {
}

AC代码

源代码

/**
 * Problem: M. Many CF Rounds vs Capoo
 * Contest: The 6th Liaoning Provincial Collegiate Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106380/problem/M
 * Created: 2026-03-12 13:41:24
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct A_b {
    ll a,b;
};
struct Cmp {
    bool operator()(const A_b &a,const A_b &b) const {
        if (a.a!=b.a) return a.a<b.a;
        return a.b>b.b;
    }
};
struct Cmp2 {
    bool operator()(const A_b &a,const A_b &b) const {
        if (a.b!=b.b) return a.b<b.b;
        return a.a<b.a;
    }
};
void Solve() {
    ll N;
    cin >> N;
    // vector<A_b> A(N+2);
    vector<A_b> safeA,dangerA;
    for (int i=1;i<=N;++i) {
        ll a,b;
        cin>>a>>b;
        if (a>=b) {
            safeA.push_back({a,b});
        }else {
            dangerA.push_back({a,b});
        }
    }
    ll ans=SZ(safeA);
    sort(all(safeA),Cmp());
    sort(all(dangerA),Cmp2());
    ll idx1=0,idx2=0;
    ll cur_ability=0;
#ifdef LOCAL
    for (int i=0;i<SZ(safeA);++i) {
        debug(i);
        debug(safeA[i].a);
        debug(safeA[i].b);
    }
    cend;
    for (int i=0;i<SZ(dangerA);++i) {
        debug(i);
        debug(dangerA[i].a);
        debug(dangerA[i].b);
    }
    cend;
#endif

    auto forward=[&]() -> bool {
        while (idx1<SZ(safeA) && idx2<SZ(dangerA) && safeA[idx1].a<dangerA[idx2].b) {
            cur_ability=max(cur_ability,safeA[idx1].b);
            ++idx1;
        }

        if (cur_ability<=dangerA[idx2].a) {
            cur_ability=max(cur_ability,dangerA[idx2].b);
            ++ans;
        }
#ifdef LOCAL
        debug(idx1);
        debug(idx2);
        debug(ans);
        debug(cur_ability);
        debug(dangerA[idx2].a);
        debug(dangerA[idx2].b);
#endif
        ++idx2;
        if (idx2<SZ(dangerA)) {
            return true;
        }
        return false;
    };
    while (forward()) {
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/

线性筛

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）3737371111≤b≤10181 \le b \le 10^{18}1≤b≤1018

基本情况

心得感悟

题目 I take from the richer

题目 Just reseat!

题目 Do you play Ballance?

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

心路历程（WA，TLE，MLE……） $37$ $1$ $1 \le b \le 10^{18}$