# Codeforces Round #685 (Div. 2)

## Subtract or Divide

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 9, INF = 1e9;
int cal(int n, int ep)
{
if (ep < 0)
return INF;
if (n == 1)
return min(0, ep);
if (n == 2)
return 1;
if (n % 2 == 0)
return 1 + cal(2, ep - 1);
int ans = 1 + cal(n - 1, ep - 1);
for (int i = 3; i * i <= n; ++i)
if (n % i == 0)
ans = min(ans, 1 + cal(i, ans - 1));
return ans;
}
int t, n;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
printf("%d\n", cal(n, INF));
}
}


#include <bits/stdc++.h>
using namespace std;
int t, n;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d", &n);
printf("%d\n", n < 4 ? n - 1 : 2 + (n & 1));
}
}


## Non-Substring Subsequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 127;
char s[N];
int t, n, q;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d%s", &n, &q, s);
for (int i = 0, l, r; i < q; ++i)
{
scanf("%d%d", &l, &r);
--l, --r;
int ans = 0;
for (int i = 0; !ans && i < l; ++i)
if (s[i] == s[l])
ans = 1;
for (int i = r + 1; !ans && i < n; ++i)
if (s[i] == s[r])
ans = 1;
printf(ans ? "YES\n" : "NO\n");
}
}
}


## String Equality

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 9;
char a[N], b[N];
int ok(int k)
{
vector<int> va(26, 0), vb(26, 0);
for (int i = 0; a[i]; ++i)
++va[a[i] - 'a'];
for (int i = 0; b[i]; ++i)
++vb[b[i] - 'a'];
for (int i = 25; i >= 1; --i)
{
while (va[i] < vb[i])
va[i] += k, va[i - 1] -= k;
if (va[i] > vb[i])
return 0;
}
return 1;
}
int t, n, k;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d%s%s", &n, &k, a, b);
printf(ok(k) ? "Yes\n" : "No\n");
}
}


## Circle Game

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, d, k;
int main()
{
for (scanf("%lld", &t); t--;)
{
scanf("%lld%lld", &d, &k);
ll x = sqrt(d * d / (2 * k * k));
printf((k * x) * (k * x) + k * (x + 1) * k * (x + 1) > d * d ? "Utkarsh\n" : "Ashish\n");
}
}


## Bitwise Queries (Hard Version)

1. 若存在 $a_i=a_j$，于是询问 AND i j，即可得到 $a_i$ 和 $a_j$ 的值，与之前的值异或可得 $a_1$ 的值。注意这里 $i,j$ 的值可以有一个是 $1$。
2. 若不存在 $a_i=a_j$，说明 $\left\lbrace a_i\right\rbrace$ 恰完整覆盖了 $\left[1,n-1\right]$。于是要考虑使用 2 次询问求得 $a_1$ 的值。
• 官方题解找了一组 $a_i\&a_j=n-1$ ，然后用了一个稍微复杂的方式推导出来，详见官方题解。
• 后来来我翻其他人的代码，发现一种更简洁的方法：此时必存在唯一的 $a_i\oplus a_1=1,a_j\oplus a_1=2$，则有 $a_i\vert a_j=\left(1\oplus a_1\right)\vert\left(2\oplus a_1\right)=a_1$（后一个等号很容易按位证明，实际上只要满足 $a_i\&a_j=0$ 即可。）

#include <bits/stdc++.h>
using namespace std;
int queries(string s, int i, int j)
{
int x;
cout << s << " " << i << " " << j << endl;
cin >> x;
return x;
}
int main()
{
int n, ansa = -1;
cin >> n;
vector<int> xorvals(n + 1), pos(n);
for (int i = 2; i <= n; ++i)
xorvals[i] = queries("XOR", 1, i);
for (int b = 1; b <= n; ++b)
{
if (pos[xorvals[b]])
{
int c = pos[xorvals[b]],
ansb = queries("AND", b, c);
ansa = ansb ^ xorvals[b];
break;
}
pos[xorvals[b]] = b;
}
if (ansa < 0)
ansa = queries("AND", 1, pos[1]) | queries("AND", 1, pos[2]);
cout << "! " << ansa;
for (int i = 2; i <= n; ++i)
cout << " " << (ansa ^ xorvals[i]);
}


## Nullify The Matrix

1. 任意在 $S$ 上的操作都会导致 $S\to S’$。
2. 对于 $S’$ 一定可以找到使得 $S’\to S$ 的转换。

#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, n, m;
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &m);
vector<int> xorsum(n + m - 1, 0);
for (int i = 0; i < n; ++i)
for (int a, j = 0; j < m; ++j)
scanf("%d", &a), xorsum[i + j] ^= a;
printf(count(xorsum.begin(), xorsum.end(), 0) != xorsum.size() ? "Ashish\n" : "Jeel\n");
}
}