满足 n^n mod m = 0 的最小 n

Question

你有一个自然数 m。

您需要编写一个函数 f(m) 来查找满足 n^nequation0 mod m 的最小正数 n。

换句话说，n^n 可以被 m 整除。

例如：

f(13) = 13
f(420) = 210
f(666) = 222
f(1234567890) = 411522630

这是我的 python 代码。

import math

def f(m: int) -> int:
    t = math.isqrt(m) + 1
    primes = [1 for i in range(0, t)]

    maxCount = 0
    factors = []
    p = 2

    result = 1

    while p < t and p < m:
        if primes[p] == 1 and m % p == 0:
            for i in range(p + p, t):
                primes[i] = 0

            c = 0
            while m % p == 0:
                m = m // p
                c += 1
            if maxCount < c:
                maxCount = c
            result *= p
            factors.append(p)
        p += 1
    factors.append(p)
    if m > 1:
        result *= m
    if maxCount <= result:
        return result
    p1 = math.ceil(maxCount / result)
    for p in primes:
        if p >= p1:
            return result * p
    return result

问题是，结果通常会比它必须的要大。 如果您以前遇到过这个问题，请帮助我如何解决这个问题。

我试图找到数学方法，而这段代码是我迄今为止所达到的。 我希望这段代码能给我带来最小的结果，但它比我预期的要大。

Answer 1

为了解决这个问题，我们将按照给定的步骤操作：

从 n = 1 开始。

检查是否 n ^n mod m = 0。 如果为 true，则返回 n。

如果为 false，则增加 n 并重复步骤 2。

下面是实现该功能的Python代码：

def f(m):
    n = 1
    while True:
        if pow(n, n, m) == 0:
            return n
        n += 1

# Test the function with given examples
print(f(13))  # 13
print(f(420))  # 210
print(f(666))  # 222
print(f(1234567890))  # 411522630

该函数使用带有三个参数的内置 pow 函数：pow(a, b, m) 计算 a^b mod m 有效。这允许程序计算以 m 为模的大幂，而不必直接计算大幂。

注意：对于非常大的 m 值，该算法可能需要相当长的时间，因为它迭代地检查 n 的每个可能值。