ZT36 小红和小紫的取素因子游戏

描述

小红和小紫拿到了一个正整数x，她们每次可以选择x的一个因子k(k>1)，把x除以k，但要求k必须是素数。小红先手，谁先不能操作谁输。假设两人都足够聪明，最终谁取得胜利？

共进行t次游戏。

输入描述：

第一行输入一个正整数t，代表游戏的轮数。
接下来的t行，每行输入一个正整数x，代表小红和小紫拿到的正整数。
1≤t≤10
1≤x≤10^9

输出描述：

对于每次游戏：
如果小红获胜，输出一行字符串"kou"
如果小紫获胜，输出一行字符串"yukari"

示例1

输入：

2
5
12

输出：

kou
kou

说明：

共有2次游戏。
第一次她们拿到的数是5，小红取5，5/5=1，小紫无法继续取数，小红获胜。
第二次她们拿到的数是12，小红取12的素因子2，12/2=6，小紫取6的素因子2，6/2=3，小红取3的素因子3，3/3=1，然后小紫无法继续取数，小红获胜。

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.给t个整数

2.对于每个整数x，有小红和小紫两个人

3.他们每次需要选择x的一个因子k，将x除以k

4.但是这个k必须是素数

5.小红先手，谁先不能操作谁输，假设两个人都足够聪明，问每次胜利者是谁

6.如果是小红输出kou如果是小紫输出yukari

二、解题思路

1.快速幂算法

三、具体步骤

使用的语言是C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>typedef __int128 int128;// 求最大公约数（欧几里得算法）
int gcd(int a, int b) {if (b == 0)return a;return gcd(b, a % b);
}// 快速幂算法
int quick_pow(int x, int p, int mod) {int ans = 1;while (p) {if (p & 1)ans = (int128)ans * x % mod;x = (int128)x * x % mod;p >>= 1;}return ans;
}// 判断素数（Miller-Rabin算法）
int Miller_Rabin(int p) {if (p < 2)return 0;if (p == 2)return 1;if (p == 3)return 1;int d = p - 1, r = 0;while (!(d & 1)) {++r;d >>= 1;}for (int k = 0; k < 10; ++k) {int a = rand() % (p - 2) + 2;int x = quick_pow(a, d, p);if (x == 1 || x == p - 1)continue;for (int i = 0; i < r - 1; ++i) {x = (int128)x * x % p;if (x == p - 1)break;}if (x != p - 1)return 0;}return 1;
}// 取绝对值函数
int ABS(int a) {return (a < 0) ? -a : a;
}// Pollard-Rho算法进行整数分解
int Pollard_Rho(int x) {int s = 0, t = 0;int c = rand() % (x - 1) + 1;int step = 0, goal = 1;int val = 1;for (goal = 1;; goal *= 2, s = t, val = 1) {for (step = 1; step <= goal; ++step) {t = ((int128)t * t + c) % x;val = (int128)val * ABS(t - s) % x;if ((step % 127) == 0) {int d = gcd(val, x);if (d > 1)return d;}}int d = gcd(val, x);if (d > 1)return d;}
}// 分解整数x的质因数，并更新最大质因数等相关操作
void fac(int x, int* max_factor) {if (x <= *max_factor || x < 2)return;if (Miller_Rabin(x)) {*max_factor = (*max_factor > x) ? *max_factor : x;return;}int p = x;while (p >= x)p = Pollard_Rho(x);while ((x % p) == 0)x /= p;fac(x, max_factor);fac(p, max_factor);
}// 从标准输入读取一个整数
int read() {int x = 0, f = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')f = -1;c = getchar();}while (c >= '0' && c <= '9') {x = x * 10 + (c - '0');c = getchar();}return f * x;
}int main() {srand((unsigned int)time(NULL));int T = read();while (T--) {int x = read();int z = 0;while (x != 1) {int max_factor = 0;z++;fac(x, &max_factor);x /= max_factor;}if (z % 2 == 1)printf("kou\n");elseprintf("yukari\n");}return 0;
}