求解质数p最小r位分组整除规则的DSA题解析

题目本质是找满足特定分组求和整除规则的最小分组长度r，规则细节可以结合样例理解：

• 当p=3时r=1：从右往左每1位划分（即取所有单个数字）求和，和能被3整除则原数可被3整除，就是日常用的3的整除判定法。
• 当p=11时r=2：从右往左每2位划分，各组代表的两位数求和，和能被11整除则原数可被11整除。
  推广到任意不等于2、5的质数p，要求的最小r，本质是数论中10在模p下的乘法阶。

任意正整数按r位从右向左分组，可以展开为如下形式：
$$N = a_0 + a_1 \cdot 10^r + a_2 \cdot 10^{2r} + ... + a_k \cdot 10^{kr}$$
其中$a_0$是最右侧r位的数值，$a_1$是右数第二组r位的数值，以此类推。
如果分组求和判定规则成立，意味着$N \equiv (a_0+a_1+...+a_k) \pmod{p}$，代入展开式可得必须满足$10^r \equiv 1 \pmod{p}$。
由于p是不等于2、5的质数，10和p互质，根据欧拉定理，$10^{p-1} \equiv 1 \pmod{p}$，因此满足条件的r一定存在，且最小的r必然是p-1的约数。

• 第一步：计算m = p-1，枚举找出m的所有正约数
• 第二步：将所有约数从小到大排序
• 第三步：依次检查每个约数r，若满足pow(10, r, p) == 1，第一个符合条件的r就是答案

注：利用快速幂计算模幂、只枚举p-1的约数而非遍历1到p-1，可以把计算复杂度降到极低，哪怕p取到题目上限近1e6也能瞬间出结果。

def find_min_r(p):
    m = p - 1
    divisors = set()
    # 枚举求所有约数
    for i in range(1, int(m ** 0.5) + 1):
        if m % i == 0:
            divisors.add(i)
            divisors.add(m // i)
    # 从小到大找第一个满足条件的r
    for r in sorted(divisors):
        if pow(10, r, p) == 1:
            return r

p = int(input())
print(find_min_r(p))

• 输入3：m=2，约数为1、2，r=1时pow(10,1,3)=1，输出1，符合样例。
• 输入11：m=10，约数为1、2、5、10，r=1时pow(10,1,11)=10≠1，r=2时pow(10,2,11)=1，输出2，符合样例。

内容的提问来源于stack exchange，提问作者kr214229