要求(a/b)%9973,但由于a很大,我们只给出n(n=a%9973)(我们给定的a必能被b整除,且gcd(b,9973) = 1)。
时间: 2023-06-05 07:47:07 浏览: 177
给定一个n数(不能被2或5整除),计算由多少个1组成的数可以被其整除
题目要求计算(a/b)%9973,但由于a很大,只给出n(n=a%9973),其中我们给定的a必能被b整除,且gcd(b,9973) = 1。
解题思路:
根据同余定理,我们有(a/b)%9973 = (a%9973)/(b%9973)^-1,其中(b%9973)^-1表示b在模9973下的逆元。
由于gcd(b,9973) = 1,根据扩展欧几里得算法,我们可以求出b在模9973下的逆元。
然后,我们只需要将n代入公式中计算即可。
代码实现:
```python
def inv(a, p):
"""
求a在模p下的逆元
"""
_, x, _ = exgcd(a, p)
return (x % p + p) % p
def exgcd(a, b):
"""
扩展欧几里得算法
"""
if b == :
return a, 1,
d, x, y = exgcd(b, a % b)
return d, y, x - (a // b) * y
n = int(input())
b = int(input())
print((n * inv(b % 9973, 9973)) % 9973)
```
阅读全文