网站 内容建设需要进一步加强,angularjs的网站模板,公司网站搭建,wordpress基于什么语言描述 小红和小紫拿到了一个正整数x#xff0c;她们每次可以选择x的一个因子k(k1)#xff0c;把x除以k#xff0c;但要求k必须是素数。小红先手#xff0c;谁先不能操作谁输。假设两人都足够聪明#xff0c;最终谁取得胜利#xff1f; 共进行t次游戏。 输入描述… 描述 小红和小紫拿到了一个正整数x她们每次可以选择x的一个因子k(k1)把x除以k但要求k必须是素数。小红先手谁先不能操作谁输。假设两人都足够聪明最终谁取得胜利 共进行t次游戏。 输入描述 第一行输入一个正整数t代表游戏的轮数。 接下来的t行每行输入一个正整数x代表小红和小紫拿到的正整数。 1≤t≤10 1≤x≤10^9 输出描述 对于每次游戏 如果小红获胜输出一行字符串kou 如果小紫获胜输出一行字符串yukari 示例1 输入 2
5
12 输出 kou
kou 说明 共有2次游戏。
第一次她们拿到的数是5小红取55/51小紫无法继续取数小红获胜。
第二次她们拿到的数是12小红取12的素因子212/26小紫取6的素因子26/23小红取3的素因子33/31然后小紫无法继续取数小红获胜。 一、问题分析
首先读题仔细看描述中的内容发现需求是
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.htypedef __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;
}
