欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 手游 > 13届省赛python A组:10.数的拆分

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

2025/4/2 23:24:10 来源:https://blog.csdn.net/qq_47461600/article/details/146888692  浏览:    关键词:13届省赛python A组:10.数的拆分

题目1 数的拆分

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

输入格式

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

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

输出格式

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

数据范围

对于 10% 的评测用例, 1 ≤ T ≤ 200 , a i ≤ 1 0 9 1≤T≤200,ai≤10^9 1T200ai109
对于 30% 的评测用例, 1 ≤ T ≤ 300 , a i ≤ 1 0 18 1≤T≤300,ai≤10^{18} 1T300ai1018
对于 60% 的评测用例, 1 ≤ T ≤ 10000 , a i ≤ 1 0 18 1≤T≤10000,ai≤10^{18} 1T10000ai1018
对于所有评测用例, 1 ≤ T ≤ 100000 , 1 ≤ a i ≤ 1 0 18 1≤T≤100000,1≤ai≤10^{18} 1T1000001ai1018

输入样例:
7
2
6
12
4
8
24
72

思路

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

  • 平方数,4,16这种
  • 立方数,8,27,这种
  • 普通的, x 1 y 1 ∗ x 2 y 2 x_1^{y1} *x_{2}^{y2} x1y1x2y2
  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 Truereturn Falsedef check2(n):#验证n是否是立方数y=int(round(n**(1/3)))while y**3<=n:if y**3==n:return Truey+=1return Falsedef get_primes(n):isprime=[True]*(n+1)isprime[0]=isprime[1]=Falseprimes=[]for i in range(2,n+1):if isprime[i]:primes.append(i)for p in primes:if i*p>n:breakisprime[i*p]=Falseif i%p==0:breakreturn primes
#提前计算or每个计算一次?
N=int(5000)#几乎对于所有题目已经够用了
primes=get_primes(N)
t=int(input())
for i in range(t):n=int(input())flag=Trueif check1(n) or check2(n):print('yes')continuefor p in primes:if p*p>n:breakif n%p==0:cnt=0while n%p==0:n//=pcnt+=1if cnt==1:flag=Falsebreakif n>1 and not(check1(n) or check2(n)):flag=Falseprint('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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词