diff options
| author | Raphael McSinyx <vn.mcsinyx@gmail.com> | 2017-02-19 22:28:52 +0700 |
|---|---|---|
| committer | Raphael McSinyx <vn.mcsinyx@gmail.com> | 2017-02-19 22:28:52 +0700 |
| commit | d40c9b81db3caff8ecca79df92241bc0c28a468c (patch) | |
| tree | 41985e48e9da1fbfb65af8105bfa0304744320bd /THT/B/QG-2016/remainder.py | |
| parent | a53c4128c29f98b5fdfd9b0e13a3bbe094d975ec (diff) | |
| download | cp-d40c9b81db3caff8ecca79df92241bc0c28a468c.tar.gz | |
Translate easy programs to Scheme
Diffstat (limited to 'THT/B/QG-2016/remainder.py')
| -rwxr-xr-x | THT/B/QG-2016/remainder.py | 13 |
1 files changed, 1 insertions, 12 deletions
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') |