题解 | #小红和小紫的取素因子游戏#

#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");
        else
            printf("yukari\n");
    }
    return 0;
}