algorithm - 给定 N，找出 A^A 能被 N 整除的最小数 A

Question

这个问题说明:

给定 N，找出 A^A 能被 N 整除的最小数 A。(N<=1.000.000.000)

例如:N=9 ，输出 A=3 (3^3 mod 9=0) ；给定 N=6 输出 A=6 (6^6 mod 6=0)。

我从 1 开始计算，直到找到合适的数字，但在我计算变量 (A^A) 期间，然后数据溢出。如何更快地找到数字 A 并且不发生数据溢出？

Answer 1

1. A 的主要因素应与 N 的质因数相同.因素较少意味着 A^A % N !=0 ，拥有更多因子是没有意义的，因为我们正在寻找最小的 A .
2. 让N有质因数分解 2^a * 3^b * 5^c ... . N 的指数数组将是 expo_N = [a,b,c...]
3. 让y = product of prime factors of N . y 的指数数组将是 [1,1,1...] . y^y 的指数数组将是 expo_y = [y,y,y...] .
4. 对于 y^y被 N 整除, expo_y[i] >= expo_N[i] for i in range(length(expo_N)) .
5. 让x = max(a,b,c...) .现在，使用上面提到的要点，y >= x满足第 4 点。如果y>=x ，你有答案。否则，继续乘法y通过 2同时y < x .

这种方法实际上并不涉及对数字求幂，因此它会超时或出错。 N 的因式分解可以在 O(sqrt(N)) 中完成, 其余操作将在 O(logN) 中完成素数。

示例 1:N = 9

1. expo_N = [3: 2] (since N = 3^2)
2. y = 3, expo_y = [3: 3]
3. 自 expo_y[i] >= expo_N[i] for all i , 答案是 A = y = 3

示例 2:N = 6

1. expo_N = [2: 1, 3: 1]
2. y = 6, expo_y = [2: 6, 3: 6]
3. 自 expo_y[i] >= expo_N[i] for all i , 答案是 A = y = 6

示例 3:N = 384

1. expo_N = [2: 7, 3: 1]
2. y = 6, expo_y = [2: 6, 3: 6]
3. expo_N[2] = 7 , 所以我们乘以 y通过 2
4. y = 2*y = 12, expo_y = [2: 24, 3: 12]
5. 现在条件满足了，所以答案是A = y = 12