题目链接：https://leetcode.cn/problems/smallest-integer-divisible-by-k/description/
模运算
如果让你计算 1234 ⋅ 6789 1234 \cdot 6789 1234⋅6789 的个位数，你会如何计算？
由于只有个位数会影响到乘积的个位数，那么 4 ⋅ 9 = 36 4\cdot 9=36 4⋅9=36 的个位数 6 6 6 就是答案。
对于 1234 + 6789 1234+6789 1234+6789 的个位数，同理， 4 + 9 = 13 4+9=13 4+9=13 的个位数 3 3 3 就是答案。
你能把这个结论抽象成数学等式吗？
一般地，涉及到取模的题目，通常会用到如下等式(上面计算的是 m = 10 m=10 m=10):
( a + b ) m o d m = ( ( a m o d m ) + ( b m o d m ) ) m o d m ( a ⋅ b ) m o d m = ( ( a m o d m ) ⋅ ( b m o d m ) ) m o d m (a+b)\bmod m = ((a\bmod m) + (b\bmod m)) \bmod m \\ (a\cdot b) \bmod m=((a\bmod m)\cdot (b\bmod m)) \bmod m (a+b)modm=((amodm)+(bmodm))modm(a⋅b)modm=((amodm)⋅(bmodm))modm
证明：根据带余除法，任意整数 a a a 都可以表示为 a = k m + r a=km+r a=km+r，这里 r r r 相当于 a m o d m a mod m a mod m。那么设 a = k 1 m + r 1 , b = k 2 m + r 2 a=k_1m+r_1,\ b=k_2m+r_2 a=k1m+r1, b=k2m+r2。
第一个等式：
(
a
+
b
)
m
o
d
m
=
(
(
k
1
+
k
2
)
m
+
r
1
+
r
2
)
m
o
d
m
=
(
r
1
+
r
2
)
m
o
d
m
=
(
(
a
m
o
d
m
)
+
(
b
m
o
d
m
)
)
m
o
d
m
\begin{aligned} &(a+b) \bmod m\\ =&((k_1+k_2) m+r_1+r_2)\bmod m\\ =&(r_1+r_2)\bmod m\\ =&((a\bmod m) + (b\bmod m)) \bmod m \end{aligned}
===(a+b)modm((k1+k2)m+r1+r2)modm(r1+r2)modm((amodm)+(bmodm))modm
即：两个数相加对某个数求余等于两个数分别求余相加之后再求余。
第二个等式：
(
a
⋅
b
)
m
o
d
m
=
(
k
1
k
2
m
2
+
(
k
1
r
2
+
k
2
r
1
)
m
+
r
1
r
2
)
m
o
d
m
=
(
r
1
r
2
)
m
o
d
m
=
(
(
a
m
o
d
m
)
⋅
(
b
m
o
d
m
)
)
m
o
d
m
\begin{aligned} &(a\cdot b) \bmod m\\ =&(k_1k_2m^2+(k_1r_2+k_2r_1)m+r_1r_2)\bmod m\\ =&(r_1r_2)\bmod m\\ =&((a\bmod m)\cdot (b\bmod m)) \bmod m \end{aligned}
===(a⋅b)modm(k1k2m2+(k1r2+k2r1)m+r1r2)modm(r1r2)modm((amodm)⋅(bmodm))modm
举例一: k = 7 k = 7 k=7
从小到大枚举 n n n，第一个能被 k k k 整除的数的长度即为答案。
1 → 11 → 111 → 1111 → 11111 → 111111 1 \rightarrow 11 \rightarrow 111 \rightarrow 1111 \rightarrow 11111 \rightarrow 111111 1→11→111→1111→11111→111111
根据前置知识，设 x x x 是上一次运算的结果(初始为1)，则下一个 n n n 模 k k k 的结果为 ( 10 x + 1 ) m o d k (10x + 1) mod k (10x+1)modk，看它是否为0。
1 → 4 ⟶ 6 ⟶ 5 ⟶ 2 ⟶ 0 1 \rightarrow 4 \longrightarrow 6 \longrightarrow 5 \longrightarrow 2 \longrightarrow 0 1→4⟶6⟶5⟶2⟶0
举例二: k = 24 k=24 k=24
如果计算结果和之前的某个数相同，由于计算规则不变，后面会无限重复下去，无法得到0。
方法一：哈希表
用哈希表记录计算结果。如果在算出0之前就遇到了在哈希表中的数字，则返回-1。
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
x = 1 % k # x 为余数
seen = set() # 创建一个无序集合，用于存储余数
while x and x not in seen: # 当余数为0或者余数重复出现，退出循环
seen.add(x)
x = (10 * x + 1) % k
return -1 if x else len(seen) + 1 # 余数不为0，返回-1，余数为0，返回len(seen)+1
复杂度分析
方法二：抽屉原理
循环 k k k 次，如果没有算出0，则返回-1。为什么？模 k k k 的结果在 [ 0 , k − 1 ] [0, k-1] [0,k−1] 中，这有 k k k 个数字。如果循环 k k k 次还没有找到0,根据鸽巢原理(抽屉原理)，必然有重复的数字。这也同时说明算法一的时间复杂度为 O ( k ) O(k) O(k)。
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
if k % 2 == 0 or k % 5 == 0:
return -1
x = 1 % k
for i in count(1): # 一定有解
if x == 0:
return i
x = (x * 10 + 1) % k
复杂度分析
itertools.count(start=0, step=1)
创建一个迭代器，它从 start 值开始，返回均匀间隔的值。常用于 map() 中的实参来生成连续的数据点。此外，还用于 zip() 来添加序列号。大致相当于：
def count(start=0, step=1):
# count(10) --> 10 11 12 13 14 ...
# count(2.5, 0.5) --> 2.5 3.0 3.5 ...
n = start
while True:
yield n
n += step
当对浮点数计数时，替换为乘法代码有时精度会更好，例如：(start + step * i for i in count())。
方法三：数学推导
设 n n n 的长度为 x x x，那么 n = 1 0 x − 1 9 n=\frac{10^x-1}{9} n=910x−1。 n n n 是 k k k 的倍数，等价于 1 0 x − 1 10^x-1 10x−1 是 9 k 9k 9k 的倍数，即 1 0 x ≡ 1 ( m o d 9 k ) 10^x \equiv 1(mod 9k) 10x≡1(mod9k) 。
那么计算 ϕ ( 9 k ) \phi(9k) ϕ(9k) 并枚举其因子 d d d，用快速幂判断 1 0 d m o d ( 9 k ) 10^d mod (9k) 10dmod(9k) 是否等于1。这一做法只需要 ( ( k ) l o g k ) (\sqrt(k)log k ) (( k)logk) 的时间。
一点优化
由于 n n n 的个位数是1，所以必然不是 2 的倍数和 5 的倍数。如果 k k k 是 2 的倍数或 5 的倍数，那么必然无解，返回 —1。否则一定有解。
证明：根据算法二，在计算过程中必然会出现两个数模 k k k 同余。设这两个数为 a = 1 0 x − 1 9 a=\frac{10^x-1}{9} a=910x−1 和 b = 1 0 y − 1 9 b=\frac{10^y-1}{9} b=910y−1，且 a > b a > b a>b。那么 a − b a-b a−b 是 k k k 的倍数。
注意 a − b = 1 0 x − 1 0 y 9 = 1 0 y ⋅ 1 0 x − y − 1 9 a-b=\frac{10^x-10^y}{9}=10^y\cdot\frac{10^{x-y}-1}{9} a−b=910x−10y=10y⋅910x−y−1。 k k k在没有因子 2 和 5 的情况下，要想整除上式，必须要整除 1 0 x − y − 1 9 \frac{10^{x-y}-1}{9} 910x−y−1，这说明 n n n 的长度可以是 x − y x-y x−y。
# 计算欧拉函数（n 以内的与 n 互质的数的个数）
def phi(n: int) -> int:
res = n
i = 2
while i * i <= n:
if n % i == 0:
res = res // i * (i - 1)
while n % i == 0:
n //= i
i += 1
if n > 1:
res = res // n * (n - 1)
return res
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
if k % 2 == 0 or k % 5 == 0:
return -1
m = phi(k * 9)
# 从小到大枚举不超过 sqrt(m) 的因子
i = 1
while i * i <= m:
if m % i == 0 and pow(10, i, k * 9) == 1:
return i
i += 1
# 从小到大枚举不低于 sqrt(m) 的因子
i -= 1
while True:
if m % i == 0 and pow(10, m // i, k * 9) == 1:
return m // i
i -= 1
复杂度分析
题目链接：https://leetcode.cn/problems/pairs-of-songs-with-total-durations-divisible-by-60/description/
1. 组合数学
遍历数组的同时用一个哈希表（或者数组）记录元素的出现次数。
遍历 time \textit{time} time：
代码实现时，用一个长为 60 的数组 cnt \textit{cnt} cnt 维护 time [ i ] m o d 60 \textit{time}[i] mod 60 time[i]mod60 的出现次数。
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
ans = 0
cnt = [0] * 60
for t in time:
# 先查询 cnt，再更新 cnt，因为题目要求 i<j
# 如果先更新，再查询，就把 i=j 的情况也考虑进去了
ans += cnt[(60 - t % 60) % 60]
cnt[t % 60] += 1
return ans
复杂度分析