大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
题目大意:两个人进行游戏,桌上有k个球,第i个球的值为1i+2i+⋯+(p−1)i%p,两个人轮流取,假设DouBiNan的值大的话就输出YES,否则输出NO。
解题思路:
首先是DouBiNan先取,所以肯定优先选取剩余中值最大的,于是不存在说DouBiNan值小的情况,仅仅有大于和小于。
然后,对于val(i)=1i+2i+⋯+(p−1)i%p来说,仅仅有当i=ϕ(p)=p−1(p为素数)时,val(i)=p−1,其它情况下val(i)=0,那么仅仅要确定说有多少个i是非0的就可以,假设是偶数则输出NO,奇数输出YES。
证明,如果p有原根g,那么1i,2i,…,(p−1)i即是g1∗i,g2∗i,…,g(p−1)∗i的一个排序,由于对于gk来说,k从1到p-1,gk均不同样,而且为1到p-1。
于是val(i)=gi∗(1−gi∗(p−1))1−gi
依据费马小定理,gi∗(p−1)%p=1
所以有val(i)=gi∗(1−1)1−gi=0
- p为质数,所以一定有原根
- 原根,即gi%p≠gj%p(i≠j且i,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账号...