1243 问题 B: 破解平方数

时间限制: 1s 内存限制: 128MB 提交: 140 解决: 73
题目描述

给出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
提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

比赛公告

新学期开学,新生也可以参加的比赛哦!