From 2f674dc80f0382f1c3178f435714960734dc9d3c Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sat, 6 Jun 2020 21:33:13 +0700 Subject: Reorganize stuff from secondary school --- 2ndary/THT/B/QG-2016/remainder.py | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) create mode 100755 2ndary/THT/B/QG-2016/remainder.py (limited to '2ndary/THT/B/QG-2016/remainder.py') diff --git a/2ndary/THT/B/QG-2016/remainder.py b/2ndary/THT/B/QG-2016/remainder.py new file mode 100755 index 0000000..6cef9df --- /dev/null +++ b/2ndary/THT/B/QG-2016/remainder.py @@ -0,0 +1,31 @@ +#!/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) -- cgit 1.4.1