D 宿命之间的对决

原题链接

题意

• 现在给定一个正整数n，小红和小紫轮流操作，每次取n的一个因子x，使得n减去x。谁先将n减到0谁输。
  小红先手操作，她想知道在双方足够聪明的情况下，谁会获得最终的胜利？

思路

1. 奇偶相加减，（同偶异奇）

设奇数a为\(2k_1 + 1\)，奇数b为\(2k_2 + 1\)，偶数c为\(2k_3\)，偶数d为\(2k_4\).(\(k\in Z\))
奇 \(-\) 奇 \(=\) 偶
\((2k_1 + 1) - (2k_2 + 1) = 2(k_1 - k_2) = 2k_{new}\)
奇 \(-\) 偶 \(=\) 奇
$(2k_1 + 1) - 2k_3 = 2(k_1 - k_3) + 1 = 2k_{new} + 1 $
偶 \(-\) 偶 \(=\) 偶
\(2k_3 - 2k_4 = 2(k_3 - k_4) = 2k_{new}\)
偶 \(-\) 奇 \(=\) 奇
\(2k_3 - (2k_1 + 1) = 2(k_3 - k_1) - 1= 2k_{new} + 1\)

2. 奇数的因子中一定没有偶数，偶数的因子中一定有奇数和偶数
   \(\Rightarrow\) 奇数只能变为偶数，偶数总能变为奇数

3. 递推

\(n = 1\)时，先手只能减去因子1变为0，因此先手必败
\(n = 2\)时，先手可以选择减去因子1，后手变为\(n = 1\)时的必败态，因此\(n = 2\)时先手必胜
\(n = 3\)时，先手只能减去因子1，后手变为\(n = 2\)时的必生态，因此\(n = 3\)时先手必败
\(n = 4\)时，先手可以选择减去因子1，后手变为\(n = 3\)时的必败态，因此\(n = 4\)时先手必胜
\(n =\)偶数,偶数总能变为奇数,奇数只能变为偶数,因此先手只要每次减为奇数就能保持自己是偶数
\(n =\)奇数,奇数只能变为偶数,偶数总能变为奇数,因此后手只要每次减为奇数就能保持自己是偶数
\(\Rightarrow\) 偶数先手总是能转变为前后已有的后手的必败态，奇数先手只能转变为前后已有的后手的必胜态
\(\Rightarrow\) 偶数先手必胜，奇数先手必败

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;

#define X first
#define Y second

typedef long long LL;
const char nl = '\n';

void solve(){
	LL n;
	cin >> n;
	if(n%2)cout << "yukari";
	else cout << "kou";

}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

		solve();
	
}