// factorization を少し速くしてみた #include #define MAX 100000000 int judge(int); void factorization(int); int power(int, int); int memo[MAX + 1]; // memo[0] は使わない int factor[9]; // 2*...*23 > MAX (23は9番目の素数) int exponent[9]; // i番目の素因数の重複度 int main(void) { int n; scanf("%d", &n); factorization(n); memo[1] = -1; printf("%s\n", judge(n) == 1 ? "Alice" : "Bob"); return 0; } int judge(int n) { if(memo[n]) { return memo[n]; } int i, j; for(i = 0; i < 9; i++) { for(j = exponent[i]; 0 < j; j--) { // exponentは0初期化されてるから大丈夫 exponent[i] -= j; int result = judge( n / power(factor[i], j) ); exponent[i] += j; if( result == -1 ) { memo[n] = 1; return memo[n]; } } } memo[n] = -1; return memo[n]; } void factorization(int n) { int i, cnt = 0; for(i = 2; i <= MAX; i++) { if(n % i == 0) { factor[cnt] = i; while(n % i == 0) { n /= i; exponent[cnt]++; } cnt++; } if(1 < n && n <= i * i) { factor[cnt] = n; exponent[cnt]++; break; } } return; } int power(int x, int y) { if(y == 0) { return 1; } else { return x * power(x, y - 1); } }