qq建设网站首页,快手刷热度推广网站,引擎搜索大全,ie不支持wordpressCF 850 C. Arpa and a game with Mojtaba#xff08;爆搜优化SG#xff09;
Problem - C - Codeforces
Arpa and a game with Mojtaba - 洛谷
思路#xff1a;显然对于每一种质因子来说操作都是独立的 #xff0c; 因此可以考虑对于每一种质因子求当前质因子的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 来说 访问值之前一定要判空
#includebits/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 pairint,intPII;#define ull unsigned long long
#define lld long double
mapint , intfactor;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);
}mapint , vectorint mp;mapvectorint , int dp;// 爆搜剪枝
//剪枝 对于 3 1 2 和 3 2 1 这两个状态显然相同 考虑每个状态用最小状态表示
//0 显然是无用状态 删掉即可int sg(vectorint now) {sort(now.begin() , now.end() , greaterint()); while(!now.back()) now.pop_back();if(dp.find(now) ! dp.end()) return dp[now];setintst;int n now.size();int maxx now[0];for(int i 1 ; i maxx ; i ) {vectorintoth 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);
