首页 > 代码库 > HDU 4861 Couple doubi(数论)

HDU 4861 Couple doubi(数论)

HDU 4861 Couple doubi

题目链接

题意:给定k,p,有k个球,每个球的值为1^i+2^i+...+(p-1)^i (mod p) (1 <= i <= k),现在两人轮流取球,最后球的值总和大的人赢,问先手是否能赢

思路:先手不可能输,非赢即平,那么只要考虑每种球的值,
利用费马小定理或欧拉定理,很容易得到该函数的循环节为p - 1,

那么i如果为p - 1的倍数,即为循环节的位置,那么每个值都为1,总和为p - 1

如果i不在循环节的位置,任取一个原根g,根据原根的性质,gi中包含了1到p - 1,那么原式等同于g1m+g2m+g3m...mod p,这是一个等比数列,利用前n项和公式,求得gm?(1?gmp?1)/(1?gm) mod p,那么在利用费马定理gmp?1 mod p=1 那么原式为0

得证原式循环节为p - 1,并且只有循环节上有值,因此只要判断原始的循环节个数是奇数个还是偶数个即可

代码:

#include <cstdio>
#include <cstring>
#include <cmath>

long long k, p;

int main() {
    while (~scanf("%lld%lld", &k, &p)) {
	if (k / (p - 1) % 2) printf("YES\n");
	else printf("NO\n");
    }
    return 0;
}