UVA10831题解
2024-08-31 15:16:02
Gerg's Cake
Gerg is having a party, and he has invited his friends. p of them have arrived already, but a are running
late. To occupy his guests, he tried playing some team games with them, but he found that it was
impossible to divide the p guests into any number of equal-sized groups of more than one person.
Luckily, he has a backup plan | a cake that he would like to share between his friends. The cake is
in the shape of a square, and Gerg insists on cutting it up into equal-sized square pieces. He wants to
reserve one slice for each of the a missing friends, and the rest of the slices have to be divided evenly
between the p remaining guests. He does not want any cake himself. Can he do it?
Input
The input will consist of several test cases. Each test case will be given as a non-negative integer a and
a positive integer p as specied above, on a line. Both a and p will t into a 32-bit signed integer. The
last line will contain `-1 -1' and should not be processed.
Output
For each test case, output `Yes' if the cake can be fairly divided and `No' otherwise.
Sample Input
1 3
1024 17
2 101
0 1
-1 -1
Sample Output
Yes
Yes
No
Yes
late. To occupy his guests, he tried playing some team games with them, but he found that it was
impossible to divide the p guests into any number of equal-sized groups of more than one person.
Luckily, he has a backup plan | a cake that he would like to share between his friends. The cake is
in the shape of a square, and Gerg insists on cutting it up into equal-sized square pieces. He wants to
reserve one slice for each of the a missing friends, and the rest of the slices have to be divided evenly
between the p remaining guests. He does not want any cake himself. Can he do it?
Input
The input will consist of several test cases. Each test case will be given as a non-negative integer a and
a positive integer p as specied above, on a line. Both a and p will t into a 32-bit signed integer. The
last line will contain `-1 -1' and should not be processed.
Output
For each test case, output `Yes' if the cake can be fairly divided and `No' otherwise.
Sample Input
1 3
1024 17
2 101
0 1
-1 -1
Sample Output
Yes
Yes
No
Yes
题意:输入a,p,问把一个正方形蛋糕分成若干个小正方形,然后分给还没到的a个人一人一个后再使得已经到的p个人正好平分。
分析:本题容易被样例误导,以为只要a+p是素数就输出“Yes”。实际上并不是这么一个回事。
假设切完之后的蛋糕有x*x个,那么就有x*x=a+n*p,其中n是一个整数。
我们对这个式子左右两边同时求余就有:x*x = a (mod p)。
联系费马小定理:x^(p-1) =1 (mod p).
就有:x^(p-1)=a^(p-1)/2=1 (mod p)
现在只要计算:a^(p-1)/2 =1 (mod p)是否成立即可。
实现过程写一个快速幂就行了,不过要注意的是底数a进行求幂运算之前应该先进行a%p否则有可能会因为溢出导致WA
AC code:
#include<bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;
ull qp(ull a,ull b,ull p)
{
ull ans=;
while(b)
{
if(b&) ans=(ans*a)%p;
a=(a*a)%p;
b>>=;
}
return ans%p;
}
int main()
{
freopen("input.txt","r",stdin);
ull a,p;
while(~scanf("%llu%llu",&a,&p))
{
if(a==-&&p==-) break;
a%=p;
if(a==) printf("Yes\n");
else
{
if(qp(a,(p-)/,p)==) printf("Yes\n");
else printf("No\n");
}
}
return ;
}
最新文章
- python随便笔记。。。
- 遍历后台的List,让前台的多选宽被选中
- Spring MVC和Struts2的比较(二)
- JXL读取写入excel表格数据
- Android 显示大图片
- HTML5 autocomplete属性、表单自动完成
- HDU 5040 Instrusive(BFS+优先队列)
- AsyncHttpClient 中的重定向和 setEnableRedirects 方法异常解决
- [转] Vue中异步错误处理
- 代码规范(RL-TOC)用更合理的方式写 JavaScript
- Qt Widgets——抽象按钮及其继承类
- 文档/视图(01):第一个Demo
- 4. mybatis实战教程(mybatis in action)之四:实现关联数据的查询
- Spring Cloud和Dubbo整合开发笔记(1)
- 第一个独特字符位置 &#183; first position unique character
- 王者荣耀交流协会 - 第6次Scrum会议
- docker 解决network has active endpoints
- 接口结构+一个selenium例子
- Hbase 表的Rowkey设计避免数据热点
- pyinstaller打包exe程序各种坑!!!