CF 850 C Arpa and a game with Mojtaba（爆搜优化SG)

CF 850 C. Arpa and a game with Mojtaba（爆搜优化SG）

Problem - C - Codeforces

Arpa and a game with Mojtaba - 洛谷

思路：显然对于每一种质因子来说操作都是独立的 ， 因此可以考虑对于每一种质因子求当前质因子的SG ， 然后考虑组合这些局面。

对于每一种质因子来说 , 问题转化成了 ， 当前状态有 n 堆石子 ，数量最多一堆的石子数量为 m 个 ， 每人每次可以选择[1 - m]中任意一个数 t ， 然后把所有数量 大于等于 t 的石子堆拿走 t 个 , 先不能操作的失败 ， 问先手获胜情况。

打表发现一点规律都没有 ， 又考虑到每一个数分解质因数后的数量很少 ， 考虑爆搜SG。

对于爆搜可以考虑两个剪枝

1. 首先对于任意一个状态 ， 排序后状态本质上不变 ， 因此可以用一个状态的最小字典序或最大字典序表示当前状态。这样方便记忆化搜索。

2. 0 对于状态是无意义的 ， 因此可以边操作边把0删去

3. 对于记忆化搜索的 map 来说 ， 访问值之前一定要判空！！！

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF = 9e9;
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;#define ull unsigned long long
#define lld long double
map<int , int>factor;int qmul(int a ,int b,int mod){//快速乘，防止数据溢出 int c = (lld) a / mod * b;int res = (ull) a * b - (ull) c * mod;return (res + mod) % mod;
}int qual(int x,int d,int p){int ans = 1;while(d){if(d & 1) ans = qmul(ans , x , p); x = qmul(x , x , p);d >>= 1;}return ans;
}int A[] = {2 , 325 , 9375 , 28178 , 450775 , 9780504 , 1795265022};//判断素数 
bool miRoben(int x){if(x < 3 || x % 2 == 0) return x == 2;int d = x - 1 , r = 0;while(d % 2 == 0){d /= 2;r += 1;}for(auto a : A){int v = qual(a,d,x);if(v == 1 || v == x - 1 || v == 0) continue;for(int i = 1 ; i <= r ; i ++){v = qmul(v , v , x);if(v == x - 1 && i != r){v = 1;break;}if(v == 1) return false;}if(v != 1)return false;//费马小定理检验 }return true;
}int Pollard_Rho(int x){int s = 0 , t = 0;int c = (int)rand() % (x - 1) + 1;int step = 0 , goal = 1;int val = 1;for(goal = 1;;goal <<= 1 , s = t , val = 1){for(step = 1 ; step <= goal ; step ++){t = (qmul(t , t , x) + c) % x;val = qmul(val , abs(t - s) , x);if(step % 127 == 0){int d = __gcd(val , x);if(d > 1) return d;}}int d = __gcd(val , x);if(d > 1) return d;}
}//分解质因子 
void find(int n){if(n == 1) return;if(miRoben(n)){factor[n] += 1;return;}int p = n;while(p == n) p = Pollard_Rho(n);find(p);find(n / p);
}map<int , vector<int>> mp;map<vector<int> , int> dp;// 爆搜剪枝
//剪枝 对于 3 1 2 和 3 2 1 这两个状态显然相同 ， 考虑每个状态用最小状态表示
//0 显然是无用状态 ，删掉即可int sg(vector<int> now) {sort(now.begin() , now.end() , greater<int>()); while(!now.back()) now.pop_back();if(dp.find(now) != dp.end()) return dp[now];set<int>st;int n = now.size();int maxx = now[0];for(int i = 1 ; i <= maxx ; i ++) {vector<int>oth = now;for(int j = 0 ; j < n ; j ++) {if(oth[j] >= i) oth[j] -= i;}st.insert(sg(oth));}for(int i = 0 ; ; i ++) if(!st.count(i)) return dp[now] = i;
}void init() {factor.clear();
}int n;signed main(){IOScin >> n;for(int i = 1 ; i <= n ; i ++) {int now; cin >> now;init();find(now);for(auto [x , y] : factor) {mp[x].push_back(y);}}int res = 0;for(auto [x , y] : mp) {res ^= sg(y); }cout << ((res == 0) ? "Arpa" : "Mojtaba");return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);