1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
//
// See ../README.md
//
//
// Run as: ln ch-1.java ch1.java; javac ch1.java; java ch1 < input-file
//
import java.util.*;
public class ch1 {
//
// Find the GCD, using Stein's algorithm
// (https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
//
public static int gcd (int u, int v) {
boolean u_odd = u % 2 != 0;
boolean v_odd = v % 2 != 0;
return u == v || v == 0 ? u
: u == 0 ? v
: !u_odd && !v_odd ? gcd (u >> 1, v >> 1) << 1
: !u_odd && v_odd ? gcd (u >> 1, v)
: u_odd && !v_odd ? gcd (u, v >> 1)
: u > v ? gcd (u - v, v)
: gcd (v - u, u);
}
//
// Return true if number is a power of n, that is, number == n ^ p
// for some non-negative integer p. Return false otherwise.
//
public static boolean is_power_of_n (int number, int n) {
return number < 1 ? false
: number == 1 ? true
: number % n != 0 ? false
: is_power_of_n (number / n, n);
}
public static boolean is_power_of_2 (int number) {
return is_power_of_n (number, 2);
}
public static void main (String [] args) {
Scanner scanner = new Scanner (System . in);
while (scanner . hasNextInt ()) {
int n = scanner . nextInt ();
int m = scanner . nextInt ();
if (n % 2 == 1 || m % 2 == 1) {
System . out . println ("0");
continue;
}
int r = gcd (n, m);
System . out . println (r > 1 && is_power_of_2 (r) ? 1 : 0);
}
}
}
|
