From d40c9b81db3caff8ecca79df92241bc0c28a468c Mon Sep 17 00:00:00 2001
From: Raphael McSinyx <vn.mcsinyx@gmail.com>
Date: Sun, 19 Feb 2017 22:28:52 +0700
Subject: Translate easy programs to Scheme

---
 THT/B/QG-2016/REMAINDER.TXT | 15 +++++++++++++++
 THT/B/QG-2016/remainder.py  | 13 +------------
 THT/B/QG-2016/remainder.scm | 20 ++++++++++++++++++++
 THT/B/QG-2016/trigrid.scm   |  6 ++++++
 4 files changed, 42 insertions(+), 12 deletions(-)
 create mode 100644 THT/B/QG-2016/remainder.scm
 create mode 100644 THT/B/QG-2016/trigrid.scm

(limited to 'THT/B/QG-2016')

diff --git a/THT/B/QG-2016/REMAINDER.TXT b/THT/B/QG-2016/REMAINDER.TXT
index e69de29..f7c3ff9 100644
--- a/THT/B/QG-2016/REMAINDER.TXT
+++ b/THT/B/QG-2016/REMAINDER.TXT
@@ -0,0 +1,15 @@
+4
+10
+792
+1
+80498
+73871642
+159372937
+484072840
+998
+14
+78632184
+8080810096
+145654824
+853815140748207456
+222510201505884864
diff --git a/THT/B/QG-2016/remainder.py b/THT/B/QG-2016/remainder.py
index 2c4de2d..c70faba 100755
--- a/THT/B/QG-2016/remainder.py
+++ b/THT/B/QG-2016/remainder.py
@@ -18,17 +18,6 @@ TESTS = [
     [123456789123456789, 123456789123456789, 987654321123456789]
 ]
 
-
-def powmod(a, n, m):
-    if n == 1:
-        return a % m
-
-    if n % 2:
-        return powmod(a, n // 2, m) ** 2 * a % m
-
-    return powmod(a, n // 2, m) ** 2 % m
-
-
 # Gọi l là "chiều dài" của x, l = int(log10(x) + 1) hay l = len(str(x))
 # Đặt l ** 10 = a, dễ thấy y = x * (a**(n-1) + a**(n-2) + ... + a + 1)
 #                            = x * (a**n - 1) / (a - 1)
@@ -40,5 +29,5 @@ with open('REMAINDER.TXT', 'w') as f:
     for case in TESTS:
         a = 10 ** len(str(case[0]))
         case[2] *= a - 1
-        p = powmod(a, case[1], case[2])
+        p = pow(a, case[1], case[2])
         f.write(str(case[0] * (p - 1) % case[2] // (a - 1)) + '\n')
diff --git a/THT/B/QG-2016/remainder.scm b/THT/B/QG-2016/remainder.scm
new file mode 100644
index 0000000..3df8468
--- /dev/null
+++ b/THT/B/QG-2016/remainder.scm
@@ -0,0 +1,20 @@
+(define (sqr x) (* x x))
+(define (pow x y z)
+  (cond ((= y 1) (remainder x z))
+         ((= (remainder y 2) 0) (remainder (sqr (pow x (quotient y 2) z)) z))
+         (else (remainder (* (sqr (pow x (quotient y 2) z)) x) z))))
+(with-output-to-file "REMAINDER.TXT" (lambda ()
+                                       (for-each
+  (lambda (l)
+    (let* ((a (integer-expt 10 (string-length (number->string (list-ref l 0)))))
+           (m (* (list-ref l 2) (- a 1)))
+           (p (pow a (list-ref l 1) m)))
+      (display (quotient (remainder (* (list-ref l 0) (- p 1)) m) (- a 1)))
+      (newline)))
+  '((12 3 8) (2 15 17) (456 6 1296) (1234 100 9) (11223344 1000000 142857)
+    (55667788 10000000 1000000007) (1357 24682468 999999999)
+    (24680 1357913579 777777777) (998 1000000000000 999)
+    (1234 11111111111111 30) (1 222222222222222 123456789)
+    (2016 666666666666666 8888888888) (11223344 555666777888999 1357924680)
+    (999999999999999967 999999999999999877 999999999999999989)
+    (123456789123456789 123456789123456789 987654321123456789)))))
diff --git a/THT/B/QG-2016/trigrid.scm b/THT/B/QG-2016/trigrid.scm
new file mode 100644
index 0000000..d99a1fd
--- /dev/null
+++ b/THT/B/QG-2016/trigrid.scm
@@ -0,0 +1,6 @@
+(with-output-to-file "TRIGRID.TXT" (lambda () (for-each
+  (lambda (a)
+    (display (remainder (quotient (* a (+ a 2) (+ (* a 2) 1)) 8) 2016))
+    (newline))
+  '(4 3 5 6 111 222 3333 4444 55555 666666 7777777 88888888 999999999
+    123456789123456789 1000000000000000000))))
-- 
cgit 1.4.1