13届省赛python A组：10.数的拆分

题目1 数的拆分

给定 T 个正整数 ai，分别问每个 ai 能否表示为 $x{1}^{y1}\cdot x{2}^{y2}$ 的形式，其中 x1,x2 为正整数，y1,y2 为大于等于 2 的正整数。

输入格式

输入第一行包含一个整数 T 表示询问次数。

接下来 T 行，每行包含一个正整数 ai。

输出格式

对于每次询问, 如果 ai 能够表示为题目描述的形式则输出 yes，否则输出 no。

数据范围

对于 10% 的评测用例，$1\le T\le 200，ai\le 10^9$；
对于 30% 的评测用例，$1\le T\le 300，ai\le 10^{18}$；
对于 60% 的评测用例，$1\le T\le 10000，ai\le 10^{18}$；
对于所有评测用例，$1\le T\le 100000，1\le ai\le 10^{18}$。

输入样例：

7
2
6
12
4
8
24
72

思路

从样例中发现输出yes的有三种情况：

• 平方数，4,16这种
• 立方数，8,27,这种
• 普通的，$x_1^{y1}\ast x_2^{y2}$

1. 注意判断立方数的时候，int(round(x**(1/3)))存在精度误差，所以采用向上逼近的方式判断
2. N为什么取5000，几乎满足所有算法题目筛质数的要求了
3. p*p>n，此时n本身是一个大质数，没必要继续分解了（任何一个合数都至少有一个质数因子<=sqrt(n)）

python代码

from math import *
def check1(n):#验证n是否是平方数
    y=int(sqrt(n))
    if y**2==n:
        return True
    return False

def check2(n):#验证n是否是立方数
    y=int(round(n**(1/3)))
    while y**3<=n:
        if y**3==n:
            return True
        y+=1
    return False

def get_primes(n):
    isprime=[True]*(n+1)
    isprime[0]=isprime[1]=False
    primes=[]
    for i in range(2,n+1):
        if isprime[i]:
            primes.append(i)
        for p in primes:
            if i*p>n:
                break
            isprime[i*p]=False
            if i%p==0:
                break
    return primes
#提前计算or每个计算一次？
N=int(5000)#几乎对于所有题目已经够用了
primes=get_primes(N)
t=int(input())
for i in range(t):
    n=int(input())
    flag=True
    if check1(n) or check2(n):
        print('yes')
        continue
    for p in primes:
        if p*p>n:
            break
        if n%p==0:
            cnt=0
            while n%p==0:
                n//=p
                cnt+=1
            if cnt==1:
                flag=False
                break
    if n>1 and not(check1(n) or check2(n)):
        flag=False
    print('yes' if flag else 'no')

知识点

蓝桥杯笔记：蓝桥杯备赛笔记

1. 埃氏筛
2. 数学知识：所有的合数n至少含有一个<=sqrt(n)的质因子
3. y=int(round(x**(1/3)))是浮点运算，需要验证y**3==x or （y+1）**3==x