数的拆分
以下为个人对赛题的一个分析，不能保证正确性，如果认为分析有问题，请批评指正。
最终代码有还有问题，为开根号的精度问题，如果是开3，7次根等，则可能误判。
问题描述
问题分析
分析一
问题正整数 a i a_i ai?能否表示为 x 1 y 1 ? x 2 y 2 x_1^{y_1}*x_2^{y_2} x1y1???x2y2??，一个朴素的想法是获取到 1 0 9 10^{9} 109 次方的素数表，然后用a去模素数表（prime_table）中的元素，当余数为零时y1加1, a = a / / p r i m e _ t a b l e [ i ] a = a// prime\_table[i] a=a//prime_table[i] 直到余数不为零，即算出了 x 1 , y 1 x_1,y_1 x1?,y1?同理算出 x 2 , y 2 x_2,y_2 x2?,y2?。即
# 获取素数表，为确定性算法。从小到大。
def get_prime_table(n):
prime_table = [2, 3, 5, 7]
if n <= 10:
return prime_table
sqrt_n = math.floor(math.sqrt(n)) + 1
for i in range(11, n + 1, 2):
j = 0
len_prime_table = len(prime_table)
flag = True
while j < len_prime_table and prime_table[j] < sqrt_n:
if i % prime_table[j] == 0:
flag = False
break
j += 1
if flag:
prime_table.append(i)
return prime_table
# n为题目中的a，prime_table为按序排列的素数表
def can_frac(n, prime_table):
prime_len = len(prime_table) # 素数表元素个数。
n_sqrt = math.floor(math.sqrt(n)) + 1 # 根号n范围内有无数的平方满足条件。
i = 0
# 遍历素数表
while i < prime_len and prime_table[i] <= n_sqrt:
x1 = n
y1 = 0
# 算出x1^{y1}
while x1 % prime_table[i] == 0:
x1 = x1 // prime_table[i]
y1 += 1
if y1 == 1: return False # 如果y1等于1不满足题意
if x1 == 1: # 如果刚好为a=x1^{y1}次方的情况。
print(prime_table[i], y1)
return True
# 此时 x1 为 a//x1^{y1}。
# 判断第二个数是否满足题意
i += 1 # i+1之前不可能有满足的数可以整除x1了
if y1 >= 2:
y1 = 0
while x1 % prime_table[i] == 0:
x1 = x1 // prime_table[i]
y1 += 1
# 如果第二个数为满足题意的数，则x1为1，y1为大于等于2的数
if y1 >= 2 and x1 == 1:
return True
else:
return False
return False
# 处理题目输入
n = int(input())
test_list = []
for i in range(n):
test_list.append(int(input()))
print(test_list)
start = time.time()
#获取素数表
pt1 = get_prime_table(10 ** 5)
for e in test_list:
if can_frac(e, pt1):
print("yes")
else:
print("no")
end = time.time()
print(end - start)
# 0.10699892044067383
以上算法只能处理 a < = 1 0 9 a<=10^9 a<=109的情况。主要耗时来源于获取素数表，求 1 0 5 10^5 105范围内素数表大约耗时0.10699892044067383
难点在于当数位 1 0 18 10^{18} 1018次方时获取素数表将非常耗时，最坏情况为一个数 x 1 x_1 x1?非常接近 1 0 9 10^{9} 109，这个数的平方为a，即 a = x 1 2 a=x_1^2 a=x12?，如果是用以上方法查素数表，首先表的素数范围为 1 0 9 10^{9} 109内的素数，其次 x 1 x_1 x1?要从2遍历到素数表末尾才能获取到 a = x 1 2 a=x_1^2 a=x12?。这两个步骤较为耗时的是获取 1 0 9 10^9 109的素数表。
start = time.time()
pt1 = get_prime_table(10 ** 6)
end = time.time()
print(end - start)
# 2.228759288787842
# 10 ** 7
#44.911319732666016
可见当获取到 1 0 7 10^7 107的素数表时，就已经不能满足题目要求的5s要求了。
所以只能考虑素数表在 1 0 5 10^5 105范围内的情况。
分析二
据题，有两种情况满足题意。
情况一
a a a是某个素数的k次方，假设 a = x 1 k a = x_1^{k} a=x1k?，其中 x 1 x_1 x1?为素数，k大于等于2。
此时考虑 x 1 x_1 x1?的范围， 2 ≤ x 1 ≤ a ≤ 1 0 18 / 2 2\le x_1\le \sqrt a \le 10^{18/2} 2≤x1?≤a?≤1018/2,如果有 x 1 x_1 x1?满足题意，必然有 x 1 = a k x_1 = \sqrt[k]a x1?=ka? 且 x 1 x_1 x1?是整数。
只要知道k的范围遍历即可。易知当 x 1 = 2 x_1 = 2 x1?=2时k有最大值为 ? l o g 2 a ? + 1 \lfloor log_2^{a}\rfloor+1 ?log2a??+1;当 x 1 = a 1 / 2 x_1=a^{1/2} x1?=a1/2时k有最小值2。
情况一解法：
即使 a = 1 0 18 a = 10^{18} a=1018,也只需要遍历60步
# 判断是否为情况1,即为一个素数的k次方的情况。
def is_case_single_num(n):
k = math.floor(math.log2(n)) + 1
for i in range(2, k + 1):#python 区间左闭右开
if math.pow(n, 1 / i).is_integer():# 这里存在问题
print(math.pow(n, 1 / i), i)#打印中间结果
return True
return False
情况2
如果 x 1 , x 2 ≠ 1 x_1,x_2\neq1 x1?,x2??=1,且 y 1 , y 2 ≥ 2 y_1,y_2\ge 2 y1?,y2?≥2, x 1 , x 2 x_1,x_2 x1?,x2?为素数。
考虑 x 1 , x 2 x_1,x_2 x1?,x2?取到最大的情况（为了查表，求出素数表的上界），显然当 y 1 , y 2 = 2 y_1,y_2=2 y1?,y2?=2时， x 1 , x 2 x_1,x_2 x1?,x2?有最大值。
即 a = ( x 1 × x 2 ) 2 a =(x_1\times x_2)^2 a=(x1?×x2?)2,此时 x 1 x 2 ≤ 1 0 18 / 2 = 1 0 9 x_1x_2\le10^{18/2}=10^9 x1?x2?≤1018/2=109,不妨假设 x 1 x_1 x1?为较小值， x 2 x_2 x2?为较大值。如果要满足题意， x 1 x_1 x1?确定了则 x 2 x_2 x2?就确定了，即 x 1 = k , x 2 = a / x 1 x_1=k,x_2=\sqrt a/x_1 x1?=k,x2?=a?/x1?,并且当 x 1 x_1 x1?增加时 x 2 x_2 x2?就会减小，并且最多当 x 1 = x 2 x_1 = x_2 x1?=x2?时如果仍无解，那么就不会有解了。
当 x 1 = x 2 时 x_1=x_2时 x1?=x2?时有 a = ( x 1 ) 4 a=(x_1)^4 a=(x1?)4，那么 x 1 x_1 x1?遍历的范围为 [ 2 , a 4 = 1 0 18 / 4 = 1 0 4.5 ] [2,\sqrt[4]a=10^{18/4}=10^{4.5}] [2,4a?=1018/4=104.5],所以素数表的范围只需要最多到 1 0 5 10^5 105即可。
通过以上分析获取到 x 1 x_1 x1?所需要遍历素数表的范围后，即可轻易解出 x 1 , y 1 x_1,y_1 x1?,y1?,而且解出 x 1 , y 1 x_1,y_1 x1?,y1?后， a / x 1 y 1 a/x_1^{y_1} a/x1y1??就退化为了情况1。至此分析完毕。
完整代码
def get_prime_table(n):
prime_table = [2, 3, 5, 7]
if n <= 10:
return prime_table
for i in range(11, n + 1, 2):
j = 0
len_prime_table = len(prime_table)
flag = True
while j < len_prime_table and prime_table[j] < math.floor(math.sqrt(n)) + 1:
if i % prime_table[j] == 0:
flag = False
break
j += 1
if flag:
prime_table.append(i)
return prime_table
# 判断是否为情况1,即为一个素数的n次方的情况。
def is_case_single_num(n):
# n_div = math.floor(math.sqrt(n)) + 1
k = math.floor(math.log2(n)) + 1
for i in range(2, k + 1):
if math.pow(n, 1 / i).is_integer():
print(math.pow(n, 1 / i), i)
return True
return False
def can_frac(n, prime_table):
x1 = n
y1 = 0
# 判断是否为情况1
if is_case_single_num(n):
return True
# n_sqrt4 = n开4次根
n_sqrt4 = math.floor(math.sqrt(math.floor(math.sqrt(n)) + 1)) + 1
prime_len = len(prime_table)
i = 0
# 遍历素数表
while i < prime_len and prime_table[i] < n_sqrt4:
# 算出x1^{y1}
while x1 % prime_table[i] == 0:
x1 = x1 // prime_table[i]
y1 += 1
if y1 == 1: return False # 如果y1等于1不满足题意
# 退化为情况1
if y1 >= 2:
if is_case_single_num(x1):
print(prime_table[i], y1)
return True
else:
return False
i += 1
return False
n = int(input())
test_list = []
for i in range(n):
test_list.append(int(input()))
start = time.time()
# xi 一定小于10^{4.5}，素数表
pt1 = get_prime_table(10 ** 5)
for e in test_list:
if can_frac(e, pt1):
print("yes")
else:
print("no")
end = time.time()
print(end - start)
100000条耗时：6.964517831802368
