HDU4861:Couple doubi（费马小定理）
2024-09-09 11:51:57
题意：
给出k个球和质数p，对每个球以公式val(i)=1^i+2^i+...+(p-1)^i (mod p)计算出它的价值，然后两个人轮流拿，最后拿到的球的总价值大的获胜，问我们先手是否获胜。
我们分成两种情况讨论：
情形1：i%(p-1)==0，即i是(p-1)的倍数，由费马小定理 a^(p-1)=1(mod p),可以套入公式得该球价值为 p-1;
情形2：i不是(p-1)的倍数，这时要用到原根的性质，对于一个正整数g和质数p，若g为p的原根，可将1,2,3...p-1表示为g^1,g^2,g^3...g^(p-1),那么带入公式可得val(i)=1^i+2^i+...+(p-1)^i (mod p)=g^i+g^(2*i)+g^(3*i)+...+g^((p-1)*i)，即可以用等比公式得到val(i)=(g^i * (g^i*(p-1) - 1)/(g^i-1)，由于费马小定理可得,val(i)=0;
那么既然val(i)只在i为(p-1)的倍数时为1，最后只要统计k是(p-1)的倍数，判断为奇则输出“YES”，否则为“NO";
相关资料：
推荐blog:
http://blog.csdn.net/keshuai19940722/article/details/38050899
http://blog.csdn.net/RaAlGhul/article/details/51882067
#include<cstdio> int k,p; int main()
{
while(scanf("%d%d",&k,&p)==)
{
k/=(p-);
if(k&) puts("YES");
else puts("NO");
}
}
最新文章
- Hammer.js--转载自李林峰的园子
- vi和vim 的常用操作
- Unity加载模块深度解析（纹理篇）
- 查看IIS哪个应用程序池占用CPU过高
- uva 10994
- hdu 4722 Good Numbers（规律题）
- Maya+3dsMax三维建模
- LeetCode (13): 3Sum Closest
- [转]解决get方法传递URL参数中文乱码问题
- JS实现单选按钮回显时页面效果出现，但选中单选框的值为空
- T-SQL 中的CROSS JOIN用法（半翻译）
- selenium处理iframe定位于切换问题解决办法
- 三小时学会Kubernetes：容器编排详细指南
- Linux 开机启动 php socket
- hdu 1576 A/B 【扩展欧几里得】【逆元】
- 每天一个linux命令(8)：scp使用
- yum和编译两种方式升级or降级Centos内核
- SpringBoot异步请求
- Linux命令:chown
- C++ 对象的定义
热门文章
- Intellij IDEA 创建消息驱动Bean - 接收JMS消息
- underscore.js 一个强大的js函数库
- epoll和poll效率差异
- python小问题记录：
- Difference between 2>&-, 2>/dev/null, |&, &>/dev/null and >/dev/null 2>&1
- IIS修改队列长度(IIS6+IIS7)
- JavaScript学习笔记（备忘录）
- Oracle中HWM与数据库性能的探讨
- 【转】This version of the rendering library is more recent than your version of ADT plug-in. Please update ADT plug-in
- Github 终于开始认真考虑开源项目许可证了