备战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程序代码】
python">n = int(input())
s = list(map(int,input().split()))
for _ in range(n):x = s[_]res,i = 0,1while i*i<=x:if x%i==0:res += 1if x//i != i:res += 1i += 1print(res)试题二：分解质因数
【题目描述】
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
【输入格式】
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
【输出格式】
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
【数据范围】
1≤n≤100,
2≤ai≤2×109
【输入样例】
python">2
6
8【输出样例】
python">2 1
3 12 3【解题思路】
模板题
【Python程序代码】
python">n = int(input())
for i in range(n):x = int(input())i = 2while i*i <= x:if x%i==0:ct = 0while x%i==0:ct+=1x//=iprint(i,ct)i += 1if x>1:print(x,1)print()试题三：质因数个数
【题目描述】
给定正整数 n，请问有多少个质数是 n 的约数。
【输入格式】
输入的第一行包含一个整数 n。
【输出格式】
输出一个整数，表示 n 的质数约数个数。
【数据范围】
对于 30%30% 的评测用例，1≤n≤10000
对于 60%60% 的评测用例，1≤n≤109
对于所有评测用例，1≤n≤1016
【输入样例】
python">396【输出样例】
python">3【解题思路】
模板题
【Python程序代码】
python">n = int(input())
i,res =2,0
while i*i<=n:if n%i==0:res += 1while n%i==0:n//=ii +=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。
【输入样例】
python">12【输出样例】
python">3【解题思路】
质因数分解，指数为计数的数相乘就是答案
【Python程序代码】
python">n = int(input())
i,res = 2,1
while i*i<=n:if n%i==0:ct = 0 while n%i==0:ct+=1n//=iif ct%2:res*=ii+= 1
if n>1:res*=n
print(res)试题五：阶乘分解
【题目描述】
给定整数 N，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。
【输入格式】
一个整数 N。
【输出格式】
N!分解质因数后的结果，共若干行，每行一对 pi,ci，表示含有 pcii 项。按照 pi 从小到大的顺序输出。
【数据范围】
3≤N≤106
【输入样例】
python">3【输出样例】
python">2 3
3 1
5 1【解题思路】
用除法解决，一个质数i在n!中的指数为n/i + n/i*i + n/i*i*i + ...
【Python程序代码】
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 = 0while primes[j]*i<=n:k = primes[j]*ist[k] = 1if i%primes[j]==0:breakj += 1
get_primes()
for i in primes:ct,t = 0,nwhile t:ct += t//it//=iprint(i,ct)
