hdu 4861 Couple doubi(数论)

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

题目链接：hdu 4861 Couple doubi

题目大意：两个人进行游戏，桌上有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

1. p为质数，所以一定有原根
2. 原根，即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;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/118365.html原文链接：https://javaforall.cn