本文共 5625 字，大约阅读时间需要 18 分钟。

题目大意

给出$n$个数，每次可以将每个数分成$k,k>1$个大小相等的数$\frac{l}{k}$，$1$不可再分，问什么时候先手会胜。

解题思路

根据SG定理，只需要考虑每个数的SG值最后再将所有的结果异或。对于每个数，显然如果是$1$必败，而如果是质数那么必胜，否则对于一个数$n$，从$2$到$n$尝试将$n$分为这么多个，显然是$n$的每对因数乘积的结果，根据SG函数的性质，设$n=p\ast q$，若$p$为偶数，那么可以得出其能到达的子局面的SG值为0（偶数个相同的数异或起来为0）；相反如果是奇数，那么最终的SG值取决于$SG(q)$，但是$n$很大，无法暴力解决。我们对前一百个数打表求$SG$值。

int sg[maxn];bitset<1005> vis;int dfs(int u) {
       if (sg[u] >= 0)        return sg[u];    vis.reset();    for (int i = 2, k; i <= u; i++) {
           if (u % i == 0) {
               k = u / i;            if (i & 1) vis[dfs(k)] = 1;            else vis[0] = 1;        }    }    for (int i = 0;; i++)        if (!vis[i]) return sg[u] = i;}void init() {
       memset(sg, -1, sizeof sg);    sg[1] = 0;    for (int i = 1; i <= 400; i++) {
           dfs(i);        cout << "(" << i << "," << sg[i] << ") ";    }}

观察找规律可知：

若一个数的质因数分解式含有$2$，无论有多少$2$对SG值的贡献只能是$1$，奇质数对SG值的贡献是该质数的个数。

那么使用PR质因数分解即可。

//// Created by Happig on 2021/1/29.//#include 
   
    #include 
    
     using namespace std;#define ENDL "\n"#define lowbit(x) (x & (-x))typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair
     
       pii;typedef pair
      
        pll;typedef pair
       
         pdd;const double eps = 1e-8;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double dinf = 1e300;const ll INF = 1e18;const int Mod = 1e9 + 7;const int maxn = 2e5 + 10;struct BigIntegerFactor {
       const static int maxm = 1e6 + 10;    ll prime[maxm], p[maxm], sz, cnt;    ll fac[10010], num[10010];    inline ll mul(ll a, ll b, ll p) {
      //wa了尝试下面的慢速乘或者改为__int128        if (p <= 1000000000) return a * b % p;        else if (p <= 1000000000000LL) return (((a * (b >> 20) % p) << 20) + (a * (b & ((1 << 20) - 1)))) % p;        else {
               ll d = (ll) floor(a * (long double) b / p + 0.5);            ll ret = (a * b - d * p) % p;            if (ret < 0) ret += p;            return ret;        }    }    inline ll slow_mul(ll a, ll b, ll Mod) {
           ll ans = 0;        while (b) {
               if (b & 1) ans = (ans + a) % Mod;            a = (a + a) % Mod;            b >>= 1;        }        return ans;    }    void init(int up) {
     //传入的参数不能超过maxm,根据数据范围来定,1e5wa了就改1e6试试        int tot = 0;        sz = up - 1;        for (int i = 1; i <= sz; i++) p[i] = i;        for (int i = 2; i <= sz; i++) {
               if (p[i] == i) prime[tot++] = i;            for (int j = 0; j < tot && 1LL * i * prime[j] <= sz; j++) {
                   p[i * prime[j]] = prime[j];                if (i % prime[j] == 0) break;            }        }    }    inline ll qkp(ll x, ll n, ll p) {
           ll ans = 1;        while (n) {
               if (n & 1) ans = mul(ans, x, p);            x = mul(x, x, p);            n >>= 1;        }        return ans;    }    inline bool check(ll a, ll n) {
           ll t = 0, u = n - 1;        while (!(u & 1)) t++, u >>= 1;        ll x = qkp(a, u, n), xx = 0;        while (t--) {
               xx = mul(x, x, n);            if (xx == 1 && x != 1 && x != n - 1) return false;            x = xx;        }        return xx == 1;    }    inline bool miller(ll n, ll k) {
     //检测一个数n是否为素数,一般k取20即可        if (n == 2) return true;        if (n < 2 || !(n & 1)) return false;        if (n <= sz) return p[n] == n;        for (int i = 0; i <= k; i++) {
               if (!check(rand() % (n - 1) + 1, n)) return false;        }        return true;    }    inline ll gcd(ll a, ll b) {
           return b == 0 ? a : gcd(b, a % b);    }    inline ll Abs(ll x) {
           return x < 0 ? -x : x;    }    inline ll Pollard_rho(ll n) {
           ll s = 0, t = 0, c = rand() % (n - 1) + 1, v = 1, ed = 1;        while (1) {
               for (int i = 1; i <= ed; i++) {
                   t = (mul(t, t, n) + c) % n;                v = mul(v, Abs(t - s), n);                if (i % 127 == 0) {
                       ll d = gcd(v, n);                    if (d > 1) return d;                }            }            ll d = gcd(v, n);            if (d > 1) return d;            s = t, v = 1, ed <<= 1;        }    }    void getfactor(ll n) {
     //得到有重复的质因子        if (n <= sz) {
               while (n != 1) fac[cnt++] = p[n], n /= p[n];            return;        }        if (miller(n, 6)) fac[cnt++] = n;        else {
               ll d = n;            while (d >= n) d = Pollard_rho(n);            getfactor(d);            getfactor(n / d);        }    }    int solve(ll x) {
      //打印"质因子-个数"        if (x == 1) return 0;        cnt = 0;        getfactor(x);        int k = 1;        num[0] = 1;        sort(fac, fac + cnt);        for (int i = 1; i < cnt; i++) {
               if (fac[i] == fac[i - 1])                num[k - 1]++;            else {
                   num[k] = 1;                fac[k++] = fac[i];            }        }        cnt = k;        int ans = 0;        for (int i = 0; i < cnt; i++) {
               if (fac[i] & 1) ans += num[i];            else ans++;            //printf("%lld %lld\n", fac[i], num[i]);        }        return ans;    }} Q;int main() {
       //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t, n;    Q.init(1000000);    cin >> t;    while (t--) {
           cin >> n;        int ans = 0;        for (int i = 1, x; i <= n; i++) {
               cin >> x;            //cout << Q.solve(x) << endl;            ans ^= Q.solve(x);        }        if (ans) cout << "W" << ENDL;        else cout << "L" << ENDL;    }    return 0;}
       
      
     
    
   

转载地址：http://jpqq.baihongyu.com/