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

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long x;
        cin>>x;
        int ans=0;
        for(int i=2;i*i<=x;i++)
        {
            while(x%i==0)
            {
                ans++;
                x/=i;
            }
        }
        if(x>1) ans++;
        if((ans&1)==1)cout<<"kou"<<'\n';
        else cout<<"yukari"<<'\n';
    }
    return 0;
}

用数论的重点是时间复杂度的优化：一个数 n 最多只会有一个大于根号 n 的“大”因子，也就是说因子除了那种种之多的情况都是小于根号n的，我们循环结束条件可以直接缩短到i*i<n最后判断剩下的质因子是不是大于1的，如果是的话就+1；这样时间复杂度就优化到根号n了。