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 
#include 
#include 

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;
}