blob: aa6b75705aac1dfda3a0e794b0fc82ba6d49cb46 (
plain)
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
61
62
63
|
;;;
;;; See ../README.md
;;;
;;;
;;; Run as: guile --no-auto-compile ch-1.scm < input-file
;;;
;;;
;;; Find the GCD, using Stein's algorithm
;;; (https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
;;;
(define (gcd u v)
(define u_odd (= (modulo u 2) 1))
(define v_odd (= (modulo v 2) 1))
(cond ((= u v) u)
((= u 0) v)
((= v 0) u)
((and (not u_odd) (not v_odd)) (ash (gcd (ash u -1) (ash v -1)) 1))
((and (not u_odd) v_odd) (gcd (ash u -1) v))
((and u_odd (not v_odd)) (gcd u (ash v -1)))
((> u v) (gcd (- u v) v))
(else (gcd (- v u) u)))
)
;;;
;;; Return #t if number is a power of n, that is, number == n ^ p
;;; for some non-negative integer p. Return #f otherwise.
;;;
(define (is-power-of-n number n)
(cond ((< number 1) #f)
((= number 1) #t)
((> (modulo number n) 0) #f)
(else (is-power-of-n (/ number n) n)))
)
(define (is-power-of-2 number)
(is-power-of-n number 2)
)
(define (main)
(define m (read))
(define n (read))
(define r)
(if (not (eof-object? m))
(begin
(display (cond ((= (modulo n 2) 1) 0)
((= (modulo m 2) 1) 0)
(else
(begin
(set! r (gcd m n))
(if (and (> r 1) (is-power-of-2 r)) 1 0)
)
)
)
)
(newline)
(main)
)
)
)
(main)
|
