[NOI Online #2 提高组]涂色游戏 题解
2024-08-24 17:24:27
题目描述
你有 1020 个格子，它们从 0 开始编号，初始时所有格子都还未染色，现在你按如下规则对它们染色：
- 编号是 p1 倍数的格子（包括 0号格子，下同）染成红色。
- 编号是 p2 倍数的格子染成蓝色。
- 编号既是 p1 倍数又是 p2 倍数的格子，你可以选择染成红色或者蓝色。
其中 p1 和 p2 是给定的整数，若格子编号是 p1 或 p2 的倍数则它必须要被染色。在忽略掉所有未染色格子后，你不希望存在 k个连续的格子颜色相同，因为你认为这种染色方案是无聊的。现在给定 p1, p2, k，你想知道是否有一种染色方案不是无聊的。
输入格式
本题包含多组数据。
第一行一个整数 T表示数据组数。
每组数据一行三个正整数p1, p2, k，变量意义见题目描述。
输出格式
对于每组数据，输出一行一个字符串，若存在一种染色方案不是无聊的，则输出 YES，否则输出 NO。
选手程序输出结果与样例或题面中的一种格式相符即可，即不区分大小写。例如，如果标准答案为 YES ，则输出结果 YES/Yes/yes 都视为正确。
输入输出样例
输入 #1
4
2 10 4
2 3 6
1 4 7
1 1 2
输出 #1
No
Yes
Yes
Yes
输入 #2
8
370359350 416913505 3
761592061 153246036 6
262185277 924417743 5
668232501 586472717 2
891054824 169842323 6
629603359 397927152 2
2614104 175031972 68
924509243 421614240 4
输出 #2
Yes
Yes
Yes
No
No
No
Yes
Yes
说明/提示
| 测试点编号 | p1, p2≤ | k≤ | T≤ |
|---|---|---|---|
| 1 ∼ 3 | 15 | 1515 | 3375 |
| 4 ∼ 6 | 10^3 | 10^3 | 10^4 |
| 7 ∼ 8 | 10^3 | 10^3 | 10 |
| 9 ∼ 10 | 10^5 | 10^3 | 10^3 |
| 11 ∼ 12 | 10^5 | 5*10^5 | 10 |
| 13 ∼ 14 | 10^5 | 5*10^5 | 10^5 |
| 15 | 10^9 | 10^9 | 10 |
| 16∼ 20 | 10^9 | 10^9 | 10^6 |
对于所有测试点1≤T≤106，1≤p1,p2,k≤109。
分析
我们设p1、p2互质，且p1<p2
那么最坏的情况就是在[k\(\times\)p2+1,(k+1)\(\times\)p2-1]之间枚举p1的倍数
区间长度=p2-2，我们只要将\(\frac{p2-2}{p1}\)+1的值与k比较就可以了
需要注意两个细节
1、k=1时要特判，直接输出No
2、p1、p2有可能不互质，要除以它们的最大公因数
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
ll gcd(ll aa,ll bb){
if(bb==0) return aa;
return gcd(bb,aa%bb);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
ll aa,bb,k;
scanf("%lld%lld%lld",&aa,&bb,&k);
ll gys=gcd(aa,bb);
aa/=gys,bb/=gys;
if(aa>bb) swap(aa,bb);
if(k==1){
printf("No\n");
continue;
}
if(bb>2 && (bb-2)/aa+1>=k) printf("No\n");
else printf("Yes\n");
}
return 0;
}
最新文章
- RunLoop（基本操作）
- while语句（1）
- [译]ngclass expressions in angularjs
- Machine Learning - 第6周（Advice for Applying Machine Learning、Machine Learning System Design）
- DevExpress汉化(WinForm)
- C# DES
- POJ 2391.Ombrophobic Bovines （最大流）
- XML入门知识
- sqlite数据库之简单操作
- laravel MethodNotAllowedHttpException错误一个原因
- Spring常用配置(二)
- lucene内存索引库、分词器
- linux各种系统下载地址
- Java利用hanlp完成语句相似度分析的案例详解
- 粗略的整改一下blog
- c/c++ sizeof运算符详解以及对象大小
- Vcenter一次性将服务器四个网卡从端口组迁移到分布式交换机的方法
- 【转发】Linux中设置服务自启动的三种方式
- python对文件的读写
- 【js】中的小技巧