diff options
author | Nguyễn Gia Phong <vn.mcsinyx@gmail.com> | 2019-12-15 15:09:13 +0700 |
---|---|---|
committer | Nguyễn Gia Phong <vn.mcsinyx@gmail.com> | 2019-12-15 15:09:13 +0700 |
commit | 9e28e4c7b67c54229df11d355047ac8a88ea1817 (patch) | |
tree | 0d9d40db69613c2c49564a3f1987a005d61f4db3 /THT/B/QG-2016/remainder.py | |
parent | 67393f42f41ab92219deb549f711121c4dab845b (diff) | |
download | cp-9e28e4c7b67c54229df11d355047ac8a88ea1817.tar.gz |
Normalize pathname
Diffstat (limited to 'THT/B/QG-2016/remainder.py')
-rwxr-xr-x | THT/B/QG-2016/remainder.py | 31 |
1 files changed, 0 insertions, 31 deletions
diff --git a/THT/B/QG-2016/remainder.py b/THT/B/QG-2016/remainder.py deleted file mode 100755 index 6cef9df..0000000 --- a/THT/B/QG-2016/remainder.py +++ /dev/null @@ -1,31 +0,0 @@ -#!/usr/bin/env python3 -TESTS = [ - [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]] - -# 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) -# y chia m bằng k dư q hay x * (a**n - 1) / (a - 1) = k * m + q -# <=> x * (a**n - 1) = k * (a*m - a) + q * (a - 1) -# <=> q = x * (a**n - 1) % (a*m - a) / (a - 1) - -with open('REMAINDER.TXT', 'w') as f: - for x, n, m in TESTS: - a = 10 ** len(str(x)) - m *= a - 1 - p = pow(a, n, m) - print(x * (p - 1) % m // (a - 1), file=f) |