結果
| 問題 | No.2 素因数ゲーム |
| コンテスト | |
| ユーザー |
 suisen
|
| 提出日時 | 2020-12-01 15:03:17 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 26,686 bytes |
| コンパイル時間 | 3,605 ms |
| コンパイル使用メモリ | 95,340 KB |
| 実行使用メモリ | 52,608 KB |
| 最終ジャッジ日時 | 2024-09-13 02:59:57 |
| 合計ジャッジ時間 | 6,324 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | RE * 31 |
ソースコード
import java.io.InputStream;
import java.util.Arrays;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
public class Main {
public static void main(String[] args) throws Exception {
ExtendedScanner sc = new ExtendedScanner();
FastPrintStream pw = new FastPrintStream();
solve(sc, pw);
sc.close();
pw.flush();
pw.close();
}
public static void solve(ExtendedScanner sc, FastPrintStream pw) {
int n = sc.nextInt();
int xor = 0;
for (int q : MathUtil.factorize(n).values()) {
xor ^= q;
}
pw.println(xor == 0 ? "Bob" : "Alice");
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
class FastScanner implements AutoCloseable {
private final ByteBuffer tokenBuf = new ByteBuffer();
private final java.io.InputStream in;
private final byte[] rawBuf = new byte[1 << 14];
private int ptr = 0;
private int buflen = 0;
public FastScanner(java.io.InputStream in) {
this.in = in;
}
public FastScanner() {
this(new java.io.FileInputStream(java.io.FileDescriptor.in));
}
private final int readByte() {
if (ptr < buflen) return rawBuf[ptr++];
ptr = 0;
try {
buflen = in.read(rawBuf);
if (buflen > 0) {
return rawBuf[ptr++];
} else {
throw new java.io.EOFException();
}
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private final int readByteUnsafe() {
if (ptr < buflen) return rawBuf[ptr++];
ptr = 0;
try {
buflen = in.read(rawBuf);
if (buflen > 0) {
return rawBuf[ptr++];
} else {
return -1;
}
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private final int skipUnprintableChars() {
int b = readByte();
while (b <= 32 || b >= 127) b = readByte();
return b;
}
private final void loadToken() {
tokenBuf.clear();
for (int b = skipUnprintableChars(); 32 < b && b < 127; b = readByteUnsafe()) {
tokenBuf.append(b);
}
}
public final boolean hasNext() {
for (int b = readByteUnsafe(); b <= 32 || b >= 127; b = readByteUnsafe()) {
if (b == -1) return false;
}
--ptr;
return true;
}
public final String next() {
loadToken();
return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
}
public final String nextLine() {
tokenBuf.clear();
for (int b = readByte(); b != '\n'; b = readByteUnsafe()) {
if (b == -1) break;
tokenBuf.append(b);
}
return new String(tokenBuf.getRawBuf(), 0, tokenBuf.size());
}
public final char nextChar() {
return (char) skipUnprintableChars();
}
public final char[] nextChars() {
loadToken();
return tokenBuf.toCharArray();
}
public final long nextLong() {
long n = 0;
boolean isNegative = false;
int b = skipUnprintableChars();
if (b == '-') {
isNegative = true;
b = readByteUnsafe();
}
if (b < '0' || '9' < b) throw new NumberFormatException();
while ('0' <= b && b <= '9') {
// -9223372036854775808 - 9223372036854775807
if (n >= 922337203685477580l) {
if (n > 922337203685477580l) {
throw new ArithmeticException("long overflow");
}
if (isNegative) {
if (b >= '9') {
throw new ArithmeticException("long overflow");
}
n = -n - (b + '0');
b = readByteUnsafe();
if ('0' <= b && b <= '9') {
throw new ArithmeticException("long overflow");
} else if (b <= 32 || b >= 127) {
return n;
} else {
throw new NumberFormatException();
}
} else {
if (b >= '8') {
throw new ArithmeticException("long overflow");
}
n = n * 10 + b - '0';
b = readByteUnsafe();
if ('0' <= b && b <= '9') {
throw new ArithmeticException("long overflow");
} else if (b <= 32 || b >= 127) {
return n;
} else {
throw new NumberFormatException();
}
}
}
n = n * 10 + b - '0';
b = readByteUnsafe();
}
if (b <= 32 || b >= 127) return isNegative ? -n : n;
throw new NumberFormatException();
}
public final int nextInt() {
long value = nextLong();
if ((int) value != value) {
throw new ArithmeticException("int overflow");
}
return (int) value;
}
public final double nextDouble() {
return Double.parseDouble(next());
}
public final void close() {
try {
in.close();
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private static final class ByteBuffer {
private static final int DEFAULT_BUF_SIZE = 1 << 12;
private byte[] buf;
private int ptr = 0;
private ByteBuffer(int capacity) {
this.buf = new byte[capacity];
}
private ByteBuffer() {
this(DEFAULT_BUF_SIZE);
}
private ByteBuffer append(int b) {
if (ptr == buf.length) {
int newLength = buf.length << 1;
byte[] newBuf = new byte[newLength];
System.arraycopy(buf, 0, newBuf, 0, buf.length);
buf = newBuf;
}
buf[ptr++] = (byte) b;
return this;
}
private char[] toCharArray() {
char[] chs = new char[ptr];
for (int i = 0; i < ptr; i++) {
chs[i] = (char) buf[i];
}
return chs;
}
private byte[] getRawBuf() {
return buf;
}
private int size() {
return ptr;
}
private void clear() {
ptr = 0;
}
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
final class ExtendedScanner extends FastScanner {
public ExtendedScanner() {super();}
public ExtendedScanner(InputStream in) {super(in);}
public int[] ints(final int n) {
final int[] a = new int[n];
Arrays.setAll(a, $ -> nextInt());
return a;
}
public int[] ints(final int n, final IntUnaryOperator f) {
final int[] a = new int[n];
Arrays.setAll(a, $ -> f.applyAsInt(nextInt()));
return a;
}
public int[][] ints(final int n, final int m) {
final int[][] a = new int[n][];
Arrays.setAll(a, $ -> ints(m));
return a;
}
public int[][] ints(final int n, final int m, final IntUnaryOperator f) {
final int[][] a = new int[n][];
Arrays.setAll(a, $ -> ints(m, f));
return a;
}
public long[] longs(final int n) {
final long[] a = new long[n];
Arrays.setAll(a, $ -> nextLong());
return a;
}
public long[] longs(final int n, final LongUnaryOperator f) {
final long[] a = new long[n];
Arrays.setAll(a, $ -> f.applyAsLong(nextLong()));
return a;
}
public long[][] longs(final int n, final int m) {
final long[][] a = new long[n][];
Arrays.setAll(a, $ -> longs(m));
return a;
}
public long[][] longs(final int n, final int m, final LongUnaryOperator f) {
final long[][] a = new long[n][];
Arrays.setAll(a, $ -> longs(m, f));
return a;
}
public char[][] charArrays(final int n) {
final char[][] c = new char[n][];
Arrays.setAll(c, $ -> nextChars());
return c;
}
public double[] doubles(final int n) {
final double[] a = new double[n];
Arrays.setAll(a, $ -> nextDouble());
return a;
}
public double[][] doubles(final int n, final int m) {
final double[][] a = new double[n][];
Arrays.setAll(a, $ -> doubles(m));
return a;
}
public String[] strings(final int n) {
final String[] s = new String[n];
Arrays.setAll(s, $ -> next());
return s;
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
class FastPrintStream implements AutoCloseable {
private static final int INT_MAX_LEN = 11;
private static final int LONG_MAX_LEN = 20;
private int precision = 9;
private static final int BUF_SIZE = 1 << 14;
private static final int BUF_SIZE_MINUS_INT_MAX_LEN = BUF_SIZE - INT_MAX_LEN;
private static final int BUF_SIZE_MINUS_LONG_MAX_LEN = BUF_SIZE - LONG_MAX_LEN;
private final byte[] buf = new byte[BUF_SIZE];
private int ptr = 0;
private final java.lang.reflect.Field strField;
private final java.nio.charset.CharsetEncoder encoder;
private final java.io.OutputStream out;
public FastPrintStream(java.io.OutputStream out) {
this.out = out;
java.lang.reflect.Field f;
try {
f = java.lang.String.class.getDeclaredField("value");
f.setAccessible(true);
} catch (NoSuchFieldException | SecurityException e) {
f = null;
}
this.strField = f;
this.encoder = java.nio.charset.StandardCharsets.US_ASCII.newEncoder();
}
public FastPrintStream(java.io.File file) throws java.io.IOException {
this(new java.io.FileOutputStream(file));
}
public FastPrintStream(java.lang.String filename) throws java.io.IOException {
this(new java.io.File(filename));
}
public FastPrintStream() {
this(new java.io.FileOutputStream(java.io.FileDescriptor.out));
}
public FastPrintStream println() {
if (ptr == BUF_SIZE) internalFlush();
buf[ptr++] = (byte) '\n';
return this;
}
public FastPrintStream println(java.lang.Object o) {
return print(o).println();
}
public FastPrintStream println(java.lang.String s) {
return print(s).println();
}
public FastPrintStream println(char[] s) {
return print(s).println();
}
public FastPrintStream println(char c) {
return print(c).println();
}
public FastPrintStream println(int x) {
return print(x).println();
}
public FastPrintStream println(long x) {
return print(x).println();
}
public FastPrintStream println(double d, int precision) {
return print(d, precision).println();
}
public FastPrintStream println(double d) {
return print(d).println();
}
private FastPrintStream print(byte[] bytes) {
int n = bytes.length;
if (ptr + n > BUF_SIZE) {
internalFlush();
try {
out.write(bytes);
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
} else {
System.arraycopy(bytes, 0, buf, ptr, n);
ptr += n;
}
return this;
}
public FastPrintStream print(java.lang.Object o) {
return print(o.toString());
}
public FastPrintStream print(java.lang.String s) {
if (strField == null) {
return print(s.getBytes());
} else {
try {
Object value = strField.get(s);
if (value instanceof byte[]) {
return print((byte[]) value);
} else {
return print((char[]) value);
}
} catch (IllegalAccessException e) {
return print(s.getBytes());
}
}
}
public FastPrintStream print(char[] s) {
try {
return print(encoder.encode(java.nio.CharBuffer.wrap(s)).array());
} catch (java.nio.charset.CharacterCodingException e) {
byte[] bytes = new byte[s.length];
for (int i = 0; i < s.length; i++) {
bytes[i] = (byte) s[i];
}
return print(bytes);
}
}
public FastPrintStream print(char c) {
if (ptr == BUF_SIZE) internalFlush();
buf[ptr++] = (byte) c;
return this;
}
public FastPrintStream print(int x) {
if (ptr > BUF_SIZE_MINUS_INT_MAX_LEN) internalFlush();
if (-10 < x && x < 10) {
if (x < 0) {
buf[ptr++] = '-';
x = -x;
}
buf[ptr++] = (byte) ('0' + x);
return this;
}
int d;
if (x < 0) {
if (x == Integer.MIN_VALUE) {
buf[ptr++] = '-'; buf[ptr++] = '2'; buf[ptr++] = '1'; buf[ptr++] = '4';
buf[ptr++] = '7'; buf[ptr++] = '4'; buf[ptr++] = '8'; buf[ptr++] = '3';
buf[ptr++] = '6'; buf[ptr++] = '4'; buf[ptr++] = '8';
return this;
}
d = len(x = -x);
buf[ptr++] = '-';
} else {
d = len(x);
}
int j = ptr += d;
while (x > 0) {
buf[--j] = (byte) ('0' + (x % 10));
x /= 10;
}
return this;
}
public FastPrintStream print(long x) {
if ((int) x == x) return print((int) x);
if (ptr > BUF_SIZE_MINUS_LONG_MAX_LEN) internalFlush();
int d;
if (x < 0) {
if (x == Long.MIN_VALUE) {
buf[ptr++] = '-'; buf[ptr++] = '9'; buf[ptr++] = '2'; buf[ptr++] = '2';
buf[ptr++] = '3'; buf[ptr++] = '3'; buf[ptr++] = '7'; buf[ptr++] = '2';
buf[ptr++] = '0'; buf[ptr++] = '3'; buf[ptr++] = '6'; buf[ptr++] = '8';
buf[ptr++] = '5'; buf[ptr++] = '4'; buf[ptr++] = '7'; buf[ptr++] = '7';
buf[ptr++] = '5'; buf[ptr++] = '8'; buf[ptr++] = '0'; buf[ptr++] = '8';
return this;
}
d = len(x = -x);
buf[ptr++] = '-';
} else {
d = len(x);
}
int j = ptr += d;
while (x > 0) {
buf[--j] = (byte) ('0' + (x % 10));
x /= 10;
}
return this;
}
public FastPrintStream print(double d, int precision) {
if (d < 0) {
print('-');
d = -d;
}
d += Math.pow(10, -precision) / 2;
print((long) d).print('.');
d -= (long) d;
for(int i = 0; i < precision; i++){
d *= 10;
print((int) d);
d -= (int) d;
}
return this;
}
public FastPrintStream print(double d) {
return print(d, precision);
}
public void setPrecision(int precision) {
this.precision = precision;
}
private void internalFlush() {
try {
out.write(buf, 0, ptr);
ptr = 0;
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
public void flush() {
try {
out.write(buf, 0, ptr);
out.flush();
ptr = 0;
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
public void close() {
try {
out.close();
} catch (java.io.IOException e) {
throw new java.io.UncheckedIOException(e);
}
}
private static int len(int x) {
return
x >= 1000000000 ? 10 :
x >= 100000000 ? 9 :
x >= 10000000 ? 8 :
x >= 1000000 ? 7 :
x >= 100000 ? 6 :
x >= 10000 ? 5 :
x >= 1000 ? 4 :
x >= 100 ? 3 :
x >= 10 ? 2 : 1;
}
private static int len(long x) {
return
x >= 1000000000000000000l ? 19 :
x >= 100000000000000000l ? 18 :
x >= 10000000000000000l ? 17 :
x >= 1000000000000000l ? 16 :
x >= 100000000000000l ? 15 :
x >= 10000000000000l ? 14 :
x >= 1000000000000l ? 13 :
x >= 100000000000l ? 12 :
x >= 10000000000l ? 11 : 10;
}
}
/**
* @author https://atcoder.jp/users/suisen
*/
final class MathUtil {
private MathUtil(){}
public static java.util.HashMap<Long, Integer> factorize(long n) {
java.util.HashMap<Long, Integer> factors = new java.util.HashMap<>();
for (long p = 2; p * p <= n; p++) {
int q = 0;
while (n % p == 0) {
n /= p;
q++;
}
if (q > 0) factors.put(p, q);
}
if (n > 1) factors.put(n, 1);
return factors;
}
public static java.util.ArrayList<Long> divisors(long n) {
java.util.ArrayList<Long> div = new java.util.ArrayList<>();
for (long i = 1; i * i <= n; i++) {
if (n % i == 0) {
div.add(i);
long j = n / i;
if (i != j) div.add(j);
}
}
return div;
}
private static java.util.HashMap<Long, Integer> mergeFactor(java.util.HashMap<Long, Integer> fac1, java.util.HashMap<Long, Integer> fac2) {
if (fac1.size() < fac2.size()) {
return mergeFactor(fac2, fac1);
}
for (java.util.Map.Entry<Long, Integer> e : fac2.entrySet()) {
long prime = e.getKey();
int num = e.getValue();
if (fac1.containsKey(prime)) {
fac1.put(prime, Math.max(fac1.get(prime), num));
} else {
fac1.put(prime, num);
}
}
return fac1;
}
public static java.util.HashMap<Long, Integer> factorizedLCM(long a, long b) {
return mergeFactor(factorize(a), factorize(b));
}
public static java.util.HashMap<Long, Integer> factorizedLCM(long... xs) {
java.util.HashMap<Long, Integer> lcm = new java.util.HashMap<>();
for (long x : xs) lcm = mergeFactor(lcm, factorize(x));
return lcm;
}
public static long lcm(long a, long b) {
return (a / gcd(a, b)) * b;
}
public static long gcd(long a, long b) {
a = Math.abs(a);
b = Math.abs(b);
if (a < b) {
long tmp = a; a = b; b = tmp;
}
if (b == 0) return a;
if (a == 0) return b;
for (long r = a % b; r != 0; r = a % b) {
a = b; b = r;
}
return b;
}
public static long gcd(long... xs) {
long gcd = 0;
for (long x : xs) gcd = gcd(gcd, x);
return gcd;
}
/**
* Return one of the solutions to {@code ax+by=gcd(a, b)}.
*
* @return {@code x}, {@code y}, {@code gcd(a, b)}.
* @param a a of ax+by=gcd(a, b).
* @param b b of ax+by=gcd(a, b).
*/
public static long[] extGCD(long a, long b) {
long s = a, sx = 1, sy = 0; // ax + by = s
long t = b, tx = 0, ty = 1; // ax + by = t
for (long tmp, u, ux, uy; s % t != 0;) {
// u: ax + by = s % t
tmp = s / t;
u = s - t * tmp; s = t ; t = u ;
ux = sx - tx * tmp; sx = tx; tx = ux;
uy = sy - ty * tmp; sy = ty; ty = uy;
}
return new long[]{tx, ty, a * tx + b * ty};
}
public static long inv(long a, long MOD) {
long b = MOD;
long u = 1, v = 0;
while (b > 0) {
long t = a / b;
a -= t * b;
long tmp1 = a; a = b; b = tmp1;
u -= t * v;
long tmp2 = u; u = v; v = tmp2;
}
u %= MOD;
return u < 0 ? u + MOD : u;
}
/**
* @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
*/
public static long[] gcdInv(long a, long mod) {
if ((a %= mod) < 0) a += mod;
if (a == 0) return new long[]{mod, 0};
long s = mod, t = a;
long m0 = 0, m1 = 1;
while (t > 0) {
long u = s / t;
s -= t * u;
m0 -= m1 * u;
long tmp;
tmp = s; s = t; t = tmp;
tmp = m0; m0 = m1; m1 = tmp;
}
if (m0 < 0) m0 += mod / s;
return new long[]{s, m0};
}
public static long pow(long a, long b, long mod) {
if (mod == 1) return 0;
if ((a %= mod) < 0) a += mod;
long pow = 1;
for (long p = a, c = 1; b > 0;) {
long lsb = b & -b;
while (lsb != c) {
c <<= 1;
p = (p * p) % mod;
}
pow = (pow * p) % mod;
b ^= lsb;
}
return pow;
}
public static java.util.OptionalLong sqrt(long a, long p) {
if ((a %= p) < 0) a += p;
if (a == 0) return java.util.OptionalLong.of(0);
if (a == 1) return java.util.OptionalLong.of(1);
if (pow(a, (p - 1) >> 1, p) != 1) return java.util.OptionalLong.empty();
if ((p & 3) == 3) {
return java.util.OptionalLong.of(pow(a, (p + 1) >> 2, p));
}
if ((p & 7) == 5) {
if (pow(a, (p - 1) >> 2, p) == 1) {
return java.util.OptionalLong.of(pow(a, (p + 3) >> 3, p));
} else {
return java.util.OptionalLong.of(pow(2, (p - 1) >> 2, p) * pow(a, (p + 3) >> 3, p) % p);
}
}
long S = 0;
long Q = p - 1;
while ((Q & 1) == 0) {
++S;
Q >>= 1;
}
long z = 1;
while (pow(z, (p - 1) >> 1, p) != p - 1) ++z;
long c = pow(z, Q, p);
long R = pow(a, (Q + 1) / 2, p);
long t = pow(a, Q, p);
long M = S;
while (t != 1) {
long cur = t;
int i;
for (i = 1; i < M; i++) {
cur = cur * cur % p;
if (cur == 1) break;
}
long b = pow(c, 1l << (M - i - 1), p);
R = R * b % p;
t = t * b % p * b % p;
c = b * b % p;
M = i;
}
return java.util.OptionalLong.of(R);
}
public static long eulerPhi(long n) {
for (long p : factorize(n).keySet()) {
n = (n / p) * (p - 1);
}
return n;
}
public static long comb(long n, long r) {
if (n < r) return 0;
r = Math.min(r, n - r);
long res = 1; for (long d = 1; d <= r; d++) {res *= n--; res /= d;}
return res;
}
public static long ceilSqrt(long n) {
long l = -1, r = n;
while (r - l > 1) {
long m = (r + l) >> 1;
if (m * m >= n) r = m;
else l = m;
}
return r;
}
public static long floorSqrt(long n) {
long l = 0, r = n + 1;
while (r - l > 1) {
long m = (r + l) >> 1;
if (m * m > n) r = m;
else l = m;
}
return l;
}
public static long[] crt(long[] r, long[] m){
if (r.length != m.length) {
throw new AssertionError("Different length.");
}
int n = r.length;
long r0 = 0, m0 = 1;
for(int i=0; i<n; i++){
if (m[i] < 1) {
throw new AssertionError();
}
long m1 = m[i];
long r1 = r[i] % m1;
if (r1 < 0) r1 += m1;
if (m0 < m1){
long tmp;
tmp = r0; r0 = r1; r1 = tmp;
tmp = m0; m0 = m1; m1 = tmp;
}
if (m0 % m1 == 0){
if (r0 % m1 != r1) return new long[]{0, 0};
continue;
}
long[] gi = gcdInv(m0, m1);
long g = gi[0], im = gi[1];
long u1 = m1 / g;
if((r1 - r0) % g != 0) return new long[]{0, 0};
long x = (r1 - r0) / g % u1 * im % u1;
r0 += x * m0;
m0 *= u1;
if (r0 < 0) r0 += m0;
}
return new long[]{r0, m0};
}
public static long garner(long[] c, long[] mods) {
int n = c.length + 1;
long[] cnst = new long[n];
long[] coef = new long[n];
java.util.Arrays.fill(coef, 1);
for (int i = 0; i < n - 1; i++) {
long m1 = mods[i];
long v = (c[i] - cnst[i] + m1) % m1;
v = v * pow(coef[i], m1 - 2, m1) % m1;
for (int j = i + 1; j < n; j++) {
long m2 = mods[j];
cnst[j] = (cnst[j] + coef[j] * v) % m2;
coef[j] = (coef[j] * m1) % m2;
}
}
return cnst[n - 1];
}
public static long floorSum(long n, long m, long a, long b){
long ans = 0;
if(a >= m){
ans += (n - 1) * n * (a / m) / 2;
a %= m;
}
if(b >= m){
ans += n * (b / m);
b %= m;
}
long ymax = (a * n + b) / m;
long xmax = ymax * m - b;
if (ymax == 0) return ans;
ans += (n - (xmax + a - 1) / a) * ymax;
ans += floorSum(ymax, a, m, (a - xmax % a) % a);
return ans;
}
/**
* @param m prime
*/
public static int primitiveRoot(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int[] divs = new int[20];
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long) i * i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) x /= i;
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2; ; g++) {
boolean ok = true;
for (int i = 0; i < cnt; i++) {
if (pow(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
}