A40977. 破解平方数
填空题
较易
知识点
题目描述
破解平方数
题目描述
给出m个数b1, b2,..., bm,每个数的素数因子都在前t个素数之内，任务是寻找这m个数的非空子集的个数x，使得每个子集的乘积都是一个完全平方数。例如t=3,则前3个素数为2, 3, 5。m=4，这4个数为9, 20, 500, 3， 每个数的素因子都是在前3个素数内，则有x=3个非空子集合{9}， {20， 500}， {9， 20， 500}，满足每个集合内的数的乘积是一个完全平方数，输出这样的集合的个数。
输入格式
每组测试数据的第一行为两个正整数t, m(1 ≤ t ≤ 100, 1 ≤ m ≤ 100) 第二行为m个数， 1 <= bi <= 109 处理至文件结束每行输出一个整数x，对应每组测试数据
输出格式
每行输出一个整数x，对应每组测试数据
样例输入
3 4
9 20 500 3
样例输出
3
参考答案
#include<stdio.h>
#include<math.h>
void count( int a[100], int m)
//a[]为存放数据的数组，m为数组有多少数据
{
int sum = 0;//用于计算符合条件的数目
int i = 1;
int j = pow(2, m) - 1;
//从1遍历到2^m-1，至于为什么细品一下
while (i <= j)
{
int q = i;//q是用来接受每次要翻译的数
int k = 0;//记录翻译到二进制哪一位
int judge = 1;//计算每个子集的乘积
while (q)
{
//若值为1，就是在这一轮的子集中，直接累乘
if (q % 2)
judge *= a[k];
q /= 2;
k++;
}
//判断是否符合条件
int judge2 = sqrt(judge);
if (judge == judge2*judge2)
sum++;
i++;//很关键( $ _ $ )
}
printf("%d\n", sum);//直接打印结果
}
int main()
{
int m, a[100];
scanf("%*d%d", &m);//不需要输入t，故第一个数据用%*d省略
while (1)
{
int i;
for (i = 0; i < m; i++)
if (scanf("%d", &a[i]) == EOF)//发现eof退出
return 0;//直接结束程序
count( a, m);
}
}
上一题
下一题