备战2024年蓝桥杯 -- 每日一题
Python大学A组
试题一：约数个数
试题二：分解质因数
试题三：质因数个数
试题四：完全平方数
试题五：阶乘分解
试题一：约数个数
【题目描述】
输入 n 个整数，依次输出每个数的约数的个数。
【输入格式】
第一行包含整数 n。
第二行包含 n 个整数 ai。
【输出格式】
共 n 行，按顺序每行输出一个给定整数的约数的个数。
【数据范围】
1≤n≤1000
1≤ai≤109
【输入样例】
5
1 3 4 6 12【输出样例】
1
2
3
4
6【解题思路】
模板题
【Python程序代码】
n = int(input())
s = list(map(int,input().split()))
for _ in range(n):
x = s[_]
res,i = 0,1
while i*i<=x:
if x%i==0:
res += 1
if x//i != i:
res += 1
i += 1
print(res)试题二：分解质因数
【题目描述】
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
【输入格式】
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
【输出格式】
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
【数据范围】
1≤n≤100,
2≤ai≤2×109
【输入样例】
2
6
8【输出样例】
2 1
3 1
2 3【解题思路】
模板题
【Python程序代码】
n = int(input())
for i in range(n):
x = int(input())
i = 2
while i*i <= x:
if x%i==0:
ct = 0
while x%i==0:
ct+=1
x//=i
print(i,ct)
i += 1
if x>1:
print(x,1)
print()试题三：质因数个数
【题目描述】
给定正整数 n，请问有多少个质数是 n 的约数。
【输入格式】
输入的第一行包含一个整数 n。
【输出格式】
输出一个整数，表示 n 的质数约数个数。
【数据范围】
对于 30%30% 的评测用例，1≤n≤10000
对于 60%60% 的评测用例，1≤n≤109
对于所有评测用例，1≤n≤1016
【输入样例】
396【输出样例】
3【解题思路】
模板题
【Python程序代码】
n = int(input())
i,res =2,0
while i*i<=n:
if n%i==0:
res += 1
while n%i==0:
n//=i
i +=1
if n>1:res +=1
print(res)试题四：完全平方数
【题目描述】
一个整数 a 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数 b，使得 a=b2。
给定一个正整数 n，请找到最小的正整数 x，使得它们的乘积是一个完全平方数。
【输入格式】
输入一行包含一个正整数 n。
【输出格式】
输出找到的最小的正整数 x。
【数据范围】
对于 30%30% 的评测用例，1≤n≤1000，答案不超过 1000。
对于 60%60% 的评测用例，1≤n≤108，答案不超过 108。
对于所有评测用例，1≤n≤1012，答案不超过 1012。
【输入样例】
12【输出样例】
3【解题思路】
质因数分解，指数为计数的数相乘就是答案
【Python程序代码】
n = int(input())
i,res = 2,1
while i*i<=n:
if n%i==0:
ct = 0
while n%i==0:
ct+=1
n//=i
if ct%2:res*=i
i+= 1
if n>1:res*=n
print(res)试题五：阶乘分解
【题目描述】
给定整数 N，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。
【输入格式】
一个整数 N。
【输出格式】
N!分解质因数后的结果，共若干行，每行一对 pi,ci，表示含有 pcii 项。按照 pi 从小到大的顺序输出。
【数据范围】
3≤N≤106
【输入样例】
3【输出样例】
2 3
3 1
5 1【解题思路】
用除法解决，一个质数i在n!中的指数为n/i + n/i*i + n/i*i*i + ...
【Python程序代码】
n = int(input())
primes,st = [],[0]*(n+10)
def get_primes():
for i in range(2,n+1):
if not st[i]:
primes.append(i)
j = 0
while primes[j]*i<=n:
k = primes[j]*i
st[k] = 1
if i%primes[j]==0:break
j += 1
get_primes()
for i in primes:
ct,t = 0,n
while t:
ct += t//i
t//=i
print(i,ct)
