CF1260C Infinite Fence 题解（扩欧）

题目地址

CF1260C

题目大意

现有\(10^{100}\)块木板需要涂漆，第x块如果是x是a的倍数，则涂一种颜色，是b的倍数，则涂另一种颜色。如果既是a又是b的倍数，那么两种颜色都可以涂；如果连续有k块板的颜色是一样的，则输出REBEL，否则输出OBEY。问是否能避免被处死。我们肯定优先使不被处死。

Solution

一周前被这个题目吊打，一周后吊打这个题目

令 \(a < b\)。b染的色就会是 \(1b,2b,...,kb\) 这些格子，而最长的颜色段应该是由 \(a\) 的倍数组成的，而且一定是在两个 \(b\) 的倍数之间。两个 \(b\) 的倍数间有 \(b-1\) 个格子，是固定的，想要让这中间 \(a\) 的倍数尽可能多，就要让段 \(a\) 的倍数中的第一个数离上一个 \(b\) 的倍数最近。假设这个距离为 \(c\)，那么就相当于满足方程：

\[ax+by=c\]

（这不就是扩展欧几里得吗！！！）别激动，我们只要考虑当这个方程有解时，\(c\) 可以取的最小的正整数是多少。所以这是裴蜀定理。因为要使这个方程有解，就要满足 \(gcd(a,b)|c\) 所以 \(c\) 最小取 \(gcd(a,b)\)

处理一下细节，最长的连续的颜色就会是 (b-gcd(a,b)-1)/a)+1 （先单独算上 \(gcd(a,b)\) 这个位置的这个 \(1\)，后面这段每 \(a\) 个数就有一个 \(1\)）

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int a,b,K;
int gcd(int a,int b) {
    return (b==0?a:gcd(b,a%b));
}
void work() {
    a = read(), b = read(), K = read();
    if(a>b) swap(a,b);
    printf("%s\n",(((b-gcd(a,b)-1)/a)+1<K?"OBEY":"REBEL"));
}
int main()
{
    int T = read();
    while(T--) work();
    return 0;
}

Summary

这道题好水呀，注意细节就OK啦