2011-0011

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

这题是SG函数的应用...

F表示状态转移，那么SG函数的定义为

g(x) = min{n ≥ 0 : n = g(y) for y ∈ F (x)}.

即非后继SG值的最小非负数

g(1) = 0

g(x) = 1, x为质数( 质数的后继只有1, g(1) = 0, 所以g(x) = 1) 

g(x*y) =2,  x,y均为质数(x*y的后继有x,y,0)

g(x*y*z) = 3

由数学归纳法可知

g(x) = x 质因数的个数

然后由SG分解定理就可得 SG = g(a1) xor g(a2) xor g(a3) ... xor g(an)

于是就转成了经典的Nim模型了。

当前状态是后手必胜态当且仅当SG = 0 

每一步决策时就把异或和跟当前的石子数g(ai)进行异或，

如果得到的结果小于当前石子数，则是合法的操作。

稍为详细一点的介绍可以看看 http://blog.csdn.net/SMCwwh/article/details/5027170 

然后就是怎么求这个质因数个数的问题了...(to be continued)...

{{{
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;


#define M 5000001
int minp[M], plist[M];
int prime(int n = M-1){
    int num = 0;
    memset(minp, 0, sizeof(minp));
    for(int i=2; i<=n; i++){
        if (!minp[i]) plist[num++] = i, minp[i] = i;
        for(int j=0;j<num&& i*plist[j]<=n;j++){
            minp[i*plist[j]] = plist[j];
            if (i%plist[j]==0) break;
        }
    }
    return num;
}


int factorize(int n){
    int num = 0;
    while(n!=1){
        n /= minp[n];
        num++;
    }
    return num;
}
int n;
int a[100000],b[100000];
int xorsum;

int main(){
    prime();
while(~scanf("%d",&n)){
        static int T = 1;
        printf("Test #%d: ",T++);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            a[i] =  factorize(a[i]); 
        }

        xorsum = 0;
        for(int i=0;i<n;i++)
            xorsum = xorsum  ^ a[i];
        if (xorsum==0){
            puts("Bob");
        }else{
            printf("Alice ");
            for(int i=0;i<n;i++)
                if ((xorsum ^ a[i]) < a[i]){
                    printf("%d\n",i+1);
                    break;
                }
            }
    }
}
}}}


by Stephen Xu

这题是SG函数的应用...

F表示状态转移，那么SG函数的定义为

g(x) = min{n ≥ 0 : n = g(y) for y ∈ F (x)}.

即非后继SG值的最小非负数

g(1) = 0

g(x) = 1, x为质数( 质数的后继只有1, g(1) = 0, 所以g(x) = 1)

g(x*y) =2, x,y均为质数(x*y的后继有x,y,0)

g(x*y*z) = 3

由数学归纳法可知

g(x) = x 质因数的个数

然后由SG分解定理就可得 SG = g(a1) xor g(a2) xor g(a3) ... xor g(an)

于是就转成了经典的Nim模型了。

当前状态是后手必胜态当且仅当SG = 0

每一步决策时就把异或和跟当前的石子数g(ai)进行异或，

如果得到的结果小于当前石子数，则是合法的操作。

稍为详细一点的介绍可以看看 http://blog.csdn.net/SMCwwh/article/details/5027170

然后就是怎么求这个质因数个数的问题了...(to be continued)...

#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define M 5000001
int minp[M], plist[M];
int prime(int n = M-1){
    int num = 0;
    memset(minp, 0, sizeof(minp));
    for(int i=2; i<=n; i++){
        if (!minp[i]) plist[num++] = i, minp[i] = i;
        for(int j=0;j<num&& i*plist[j]<=n;j++){
            minp[i*plist[j]] = plist[j];
            if (i%plist[j]==0) break;
        }
    }
    return num;
}
int factorize(int n){
    int num = 0;
    while(n!=1){
        n /= minp[n];
        num++;
    }
    return num;
}
int n;
int a[100000],b[100000];
int xorsum;
int main(){
    prime();
while(~scanf("%d",&n)){
        static int T = 1;
        printf("Test #%d: ",T++);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            a[i] =  factorize(a[i]); 
        }
        xorsum = 0;
        for(int i=0;i<n;i++)
            xorsum = xorsum  ^ a[i];
        if (xorsum==0){
            puts("Bob");
        }else{
            printf("Alice ");
            for(int i=0;i<n;i++)
                if ((xorsum ^ a[i]) < a[i]){
                    printf("%d\n",i+1);
                    break;
                }
            }
    }
}

by Stephen Xu