时间戳

首页 > 解决方案 > 求 m 的两个除数，d1>1 和 d2>1，其中 gcd(d1+d2, m)=1

python - 求 m 的两个除数，d1>1 和 d2>1，其中 gcd(d1+d2, m)=1

问题描述

我正在尝试关于 CodeForces 的两个除数问题。它需要计算答案的主要因素。

但不知何故，即使在实施 Eratosthenes 算法之后，我的代码仍显示 TIME LIMIT EXCEEDED。以下是我的代码供参考。如果能提供任何帮助，我将不胜感激。

def eratosthenes(n):
    l=[]

    status=[1 for i in range(n+1)]
    for i in range(2,n+1):
        if status[i]:
            if n%i==0:
                l.append(i)
            for j in range(i*i, n+1, i):
                status[j]=0
    # print(l)
    return l

n = int(input())
arr = list(map(int, input().split()))
l1 = [-1 for i in range(n)]
l2 = [-1 for i in range(n)]

for i in range(n):
    primeDivisors= (eratosthenes(arr[I]))
    # print(primeDivisors)
    if len(primeDivisors)<=1:
        continue

    l1[i]=primeDivisors[0]
    l2[i]=primeDivisors[1]


for i in range(n):
    print(l1[i],end=" ")
print()
for i in range(n):
    print(l2[i],end=" ")

问题陈述

给你 n 个整数 a1,a2,…,an。

对于每个 ai 找到它的两个除数 d1>1 和 d2>1 使得 gcd(d1+d2,ai)=1（其中 gcd(a,b) 是 a 和 b 的最大公约数）或者说没有这样的一对。

输入

第一行包含单个整数 n (1≤n≤5⋅10^5) — 数组 a 的大小。

第二行包含 n 个整数 a1,a2,…,an (2≤ai≤10^7) — 数组 a。

输出

为了加快输出，打印两行，每行 n 个整数。

第一行和第二行中的第 i 个整数应该是对应的除数 d1>1 和 d2>1 使得 gcd(d1+d2,ai)=1 或 -1 和 -1 如果没有这样的对。如果有多个答案，请打印其中任何一个。

标签： pythonalgorithmmathfactors

解决方案

您使用素数除数是正确的。对于互质数p和q（质数必然是），

gcd(p + q, p*q) = 1

因为如果有一些素数可以分开说por qin p*qand 分开(p + q)，它必然会分开pand q，但这会与它们互质相矛盾。

不幸的是，即使我们要选择素数p和q，我们也不能将此语句扩展为：

gcd(p + q, p^m * q^n * other_prime_powers) = 1

因为一个除数other_prime_powers可以除(p + q)，例如gcd(3 + 11 = 14, 3*11*2) != 1。（在我们的例子中，p^m * q^n * other_prime_powers, 将是A[i]，输入元素，并且p和q是它的任意两个大于 1 的因数。）

但是我们可以人为地构造出所有 的主要权力的划分A[i]，然后我们可以说，

gcd(a*b*c... + x*y*z..., a*b*c...*x*y*z...) = 1

因为我们保证 的任何除数A[i]，它划分分区的一侧，比如说x*y*z...，不能同时划分这两个部分。

对于每个元素，将其素数分解为两个任意乘积；如果元素是素幂，则将其答案设置为 -1。

从技术上讲，要创建分区，我们只需要找到A[i]s 的素数之一 P，然后除以A[i]P。

推荐阅读