题解 CF1260C 【Infinite Fence】

那个晚上,1260C将我的名字颜色,彻底地改变了——《抱零之子》
题目链接

Solution CF1260C

题目大意:给定一段长为\(10^{100}\)的木板,编号从\(0\)到\(10^{100}-1\),给定\(r,b,k \leq 10^9\),如果木板编号被\(r\)整除则必须刷成红色,被\(b\)整除必须刷成蓝色,如果同时被\(r,b\)整除可以任意刷颜色,问是否存在一种合法方案

分析:

\(10^{100}\)可以当做无限大了

首先我们假定\(r,b\)互质,否则由于木板无限长以及我们只需要判断是否有解,我们将\(r,b\)都除以\(gcd(r,b)\)不会影响答案

假定\(r<b\),然后我们就可以非常愉快的判断了

此时\(r,b\)互质,我们假定无解,那么连续\(k\)段红色有\(r(k-1)+1\)长,其中不应该有蓝色木板,所以如果\(r(k-1)+1<b\)无解,否则有解

#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
int gcd(int a,int b){return !b ? a : gcd(b,a % b);}
int t,r,b,k;
inline void solve(){
    scanf("%d %d %d",&r,&b,&k);
    int w = gcd(r,b);
    r /= w;
    b /= w;
    if(r > b)swap(r,b);
    if(ll(k - 1) * r + 1 < b)puts("REBEL");
    else puts("OBEY");
}
int main(){
    scanf("%d",&t);
    while(t--)solve();
    return 0;
}
上一篇:线性表之五,C++代码(学堂在线,华南理工大学)


下一篇:CF1221D 【Make The Fence Great Again】