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

因子题我们首先关注数据范围

如果 t 和 x 都是 1e5 左右的大小，我们可以选择暴力预处理出每个数的因子个数储存下来，然后实现O1的查询

本题 t=10 而 x 是 1e9 的范围，显然我们只需要求出这至多十个数的因子个数即可，对于一个 1e9 范围内的数，遍历 1e9 范围内的数是不是其因子是行不通的，时间复杂度是 O(n) ，但是我们小学二年级的时候学过，一个数 n 最多只会有一个大于根号 n 的“大”因子，所以我们只需要遍历根号范围内的数，然后顺便将其除掉，那么最后如果剩下了一个1，代表这个数 n 没有大于根号 n 的因子了，而如果是其他数，那么一定是一个“大”质数，我们就可以只用根号 n 的时间复杂度做出这道题了

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int __t = 1, n;
void solve() {
    cin >> n;
    int sum = 0;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            sum++;
            n /= i;
        }
    }
    if (n > 1)
        sum++;
    cout << (sum % 2 ? "kou\n" : "yukari\n");
    return;
}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cin >> __t;
    while (__t--)
        solve();
    return 0;
}