首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。