hdu 4861 Couple doubi(数论)

hdu 4861 Couple doubi(数论)

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

题目链接:hdu 4861 Couple doubi

题目大意:两个人进行游戏,桌上有k个球,第i个球的值为1i+2i++(p1)i%p,两个人轮流取,假设DouBiNan的值大的话就输出YES,否则输出NO。

解题思路:
首先是DouBiNan先取,所以肯定优先选取剩余中值最大的,于是不存在说DouBiNan值小的情况,仅仅有大于和小于。
然后,对于val(i)=1i+2i++(p1)i%p来说,仅仅有当i=ϕ(p)=p1p时,val(i)=p1,其它情况下val(i)=0,那么仅仅要确定说有多少个i是非0的就可以,假设是偶数则输出NO,奇数输出YES。

证明,如果p有原根g,那么1i,2i,,(p1)i即是g1i,g2i,,g(p1)i的一个排序,由于对于gk来说,k从1到p-1,gk均不同样,而且为1到p-1。
于是val(i)=gi(1gi(p1))1gi
依据费马小定理,gi(p1)%p=1
所以有val(i)=gi(11)1gi=0

  1. p为质数,所以一定有原根
  2. 原根,即gi%pgj%p(iji,j<p)
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;
typedef long long ll;
ll k, p;

int main () {
    while (cin >> k >> p) {
        ll t = k / (p-1);    
        if (t&1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118365.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 关于集合中一些常考的知识点总结「建议收藏」

    关于集合中一些常考的知识点总结「建议收藏」本章主要总结了集合的一些基础但有重点的知识点,例如他们的底层数据结构以及集合之间的区别,其中HashMap最为重点。集合Java的集合框架中可以分为两大类:第一类是按照单个元素存储的Co

  • 完整的蓝屏错误代码大全详解[通俗易懂]

    完整的蓝屏错误代码大全详解[通俗易懂]完整的BSOD错误代码列表从STOP0x1到STOP0xC0000221一个死机(BSOD)的蓝屏,技术上称为一个STOP错误,若在Windows遭受了严重的错误,被迫“停”的问题。在任何Windows操作系统中都会出现BSOD错误,包括Windows10,Windows8,Windows7,WindowsVista,WindowsXP甚至Windows98/95。由于蓝屏错误让…

  • 点滴的积累—J2SE学习小结

    点滴的积累—J2SE学习小结

    2021年12月14日
  • 新手入侵笔记_探灵笔记适合新手的角色

    新手入侵笔记_探灵笔记适合新手的角色【拿shell】 1.直接上传aspasajspcerphpaspxhtrcdx格式的木马,不行就利用IIS6.0解析漏洞”:1.asp;1.jpg/1.asp;.jpg/1.asp;jpg/1.asp;.xls 2.上传图片木马遇到拦截系统,连图片木马都上传不了,记事本打开图片木马在代码最前面加上gif89a,一般就能逃过拦截系统了。 3.上传图片木马把地址复制到…

  • jasypt 原理_litmp试剂

    jasypt 原理_litmp试剂文章目录一、jasypt的启动类加载二、jasypt中Encryptor、Detector和Resolver加载三、jasypt中EnableEncryptablePropertiesBeanFactoryPostProcesso四、proxy代理方式增强propertySources五、wrapper包装类方式增强propertySources六、resolver中属性值解密作者:史佳健推荐理由:文章详尽并有对应分析说明一、jasypt的启动类加载引入了jasypt-spring-boot-st

  • python3.9多线程_python多线程原理

    python3.9多线程_python多线程原理什么是线程?线程也叫轻量级进程,是操作系统能够进行运算调度的最小单位,它被包涵在进程之中,是进程中的实际运作单位。线程自己不拥有系统资源,只拥有一点儿在运行中必不可少的资源,但它可与同属一个进程的其

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号