题解#G. Remove the Prime#

(G. Remove the Prime)[https://codeforces.com/gym/103260/problem/G]

题意：

对于连续序列，两个人执行操作，对[l,r]区间指定一个被这些数字都可以整除的质数，使得区间内所有数字被该素数除至不能再除
重复操作至所有数字变为1
先后手均使用最优解，求谁赢。

题解：

首先是考虑所有数字均做一次pollard-rho，求所有数字的质因数序列。然后求所有质数的连续操作序列，记录长度。

此时我们就会得到一个小小的博弈状态。对于每个人都可以通过[l,r]操作变成下一个状态。这有点类似nimu博弈。

我们将状态列出来，得到当操作长度为 $k$ 时，若我们从中间抓取，可能会拆成两个数字，但是根据nimu博弈规则，若有两个石子堆均满足个数为n，那么只要操作镜像就可以实现后手胜利。因此，这里的操作拆成了两个数字，并不影响尼姆的结论，后手胜利当且仅当存在镜像操作可以从头做到尾。

因此结果就是nimu和是否为0

代码：

#include<bits/stdc++.h>
#include<map>
#include<random>
using namespace std;
#define ll long long
mt19937 rd((ll)(new int));
typedef __int128 lll;

// const int test_int[]={2,7,61};
ll gcd(ll a, ll b)
{
	return b == 0 ? a : gcd(b, a % b);
}


#define __gcd gcd


const ll test[] = { 2,325,9375,28178,450775,9780504,1795265022 };
ll qpow(ll x, ll n, ll mod) {
	ll c = 1;
	for (x %= mod; n; n /= 2, x = (lll)x * x % mod)
		if (n & 1) c = (lll)c * x % mod;
	return c;
}
int miller_robin(ll n) {
	if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
	ll q = __builtin_ctzll(n - 1), m = (n - 1) >> q;
	for (ll a : test) {
		if (a >= n) break;
		ll x = qpow(a, m, n), x1, i = q;
		for (; i-- && x != 1; x = x1) {
			x1 = (lll)x * x % n;
			if (x1 == 1 && x != 1 && x != n - 1) return 0;
		}
		if (x != 1) return 0;
	}
	return 1;
}
map<ll, ll> ans;
ll pollard_rho(ll x) {
	ll s = 0, t = 0, c = rd() % (x - 1) + 1, d = 1;
	for (ll val, step, g = 1; d == 1; g <<= 1, s = t) {
		val = 1;
		for (step = 1; d == 1 && step <= g; step++) {
			t = ((lll)t * t + c) % x;
			val = (lll)val * abs(t - s) % x;
			if (step % 100 == 0) d = __gcd(val, x);
		}
		d = __gcd(val, x);
	}
	return d;
}
void fac(ll n) {
	if (n < 2) return;
	if (miller_robin(n)) {
		ans[n]++; return;
	}
	ll p = n;
	while (p >= n) p = pollard_rho(n);
	fac(n / p), fac(p);
}
const int maxn = 1e4 + 5;
ll x[maxn];
vector<int>ve[2000];
vector<int>res;
void solve() {
	ll n;
	scanf("%lld", &n);

	for (int i = 1; i <= n; i++) {
		cin >> x[i];
		//if (miller_robin(x[i]))ve[i].push_back(x[i]);
		ans.clear();
		fac(x[i]);
		for (auto k : ans) {
			ve[i].push_back(k.first);
		}
	}
	ll cnt = 0;

	for (int i = 1; i <= n; i++) {
		for (auto k : ve[i]) {
			ll f = 1;
			for (int j = i + 1; j <= n; j++) {
				auto tmp = lower_bound(ve[j].begin(), ve[j].end(), k);
				if (*tmp == k) {
					f++;
					ve[j].erase(tmp);
				}
				else {
					break;
				}
			}
			cnt ^= f;
			res.push_back(f);
		}
	}
	if (cnt)cout << "First\n";
	else cout << "Second\n";
	//if (miller_robin(n)) return void(puts("Prime"));
	//ans.clear();
	//fac(n);
	//printf("%lld\n", ans.rbegin()->first);
	// for(auto [l,r]:ans) printf("%lld %lld\n",l,r);
}
int main(){
    solve();
}

题解#G. Remove the Prime#

tag:

题意：

题解：

代码：