一条咸鱼

用户名：1127673788

访问量：2056

签　名：

我走在没有你的夜里，冷冰冰（破音）

等　　级
排　　名	1773
经　　验	2544
参赛次数	4
文章发表	2
年　　龄	0
在职情况	学生
学　　校	东莞理工学院
专　　业	起飞

　　自我简介：

AC就内个芜湖！！起飞 WA就内个，你只看到第二层，而你把我想成第一层，实际上我是第五层 CE就内个你在赣神魔

TA的其他文章

1250-素数回文(C语言) 时间复杂度大优化！！好像其他解都没有我快
浏览：786

你可能喜欢

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

破解平方数-题解(C语言代码)

　　作者: 一条咸鱼　　　　发表时间：2020-02-26 14:51:46 浏览：817　|　评论：1　

原题链接：破解平方数

大家好，本人第一次写题解，可能会写得不好，见谅。（~~第一次写不知道写什么开场白~~）

------------

首先，要知道怎么判断平方数。这个挺简单的，只要
`int a2 = sqrt(a);`然后再用`if (a == a2*a2)`就可以判断a是否为平方数了。。
（~~我不会告诉你们我一开始是用，平方数的约数个数为奇数个，这个性质来判断的，饶了一大圈。。。~~）做完第1228题的后遗症，看到质数、约数相关的，满脑子骚操作(￣_￣|||)
再稍微吐槽一下，（~~输入数据中的t是没有用的~~），不！t可以约束数据的大小！(☆▽☆)

------------

接着，遍历所有情况。这道题，如果直接用for（）循环遍历，会发现有点难实现。因为，它的出循环条件，会随着输入的数据改变。所以，要用稍微灵活的方法遍历。

你会发现题目中的有个“非空子集合”这个字符串（~~为什么这个人说话这么奇怪，好想打他~~）

我自己比较习惯用2进制数来处理遍历子集，大概说说原理：

比如，{500 20 9}的子集就可以用2进制数表示
{}  -----对应------   000（2进制）--0（10进制）
{9}------对应-----001（2进制）--1（10进制）
{20}-----对应-----010（2进制）--2（10进制）
{20 9}----对应----011（2进制）--3（10进制）
{500}-----对应----100（2进制）--4（10进制）
{500 9}----对应---101（2进制）--5（10进制）
{500 20}--对应----110（2进制）--6（10进制）
{500 20 9}--对应--111（2进制）--7（10进制）

现在应该很明朗了吧，只要从0遍历到2^m-1(上面的例子是m=3)，再把它翻译成二进制数就OK了。

原题中，要求“非空子集合”，所以把空集的情况去掉，就是从1遍历到2^m-1。
有更好的方法，请一定要评论告诉我（~~写这个文章的人真的奇怪，为什么别人要告诉你。。。~~）

------------

最后，遍历判断，打印结果

附上AC代码
```c
#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);
	}
}
```

最后的最后，中国加油！武汉加油！我相信我们一定能打赢抗击武汉肺炎的战役

0.0分

3 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

看看我写的DFS?没想到这题数据这么水，本来我以为铁定超时或者爆long long，没想到居然AC了

2020-03-31 10:15:49

一条咸鱼

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求素数问题（C语言代码）

破解平方数-题解(C语言代码)

评论区

精彩推荐

A+B for Input-Output Practice (VII) （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【排队买票】（C语言代码）

WU-输入输出格式练习（C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

字符删除（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C二级辅导-统计字符（C语言描述——用函数求解）

一条咸鱼

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C二级辅导-温度转换 （C语言代码）

C语言训练-8除不尽的数 （C语言代码）暴力解法，答案只有一个，直接输出就好了

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求素数问题 （C语言代码）

破解平方数-题解(C语言代码)

评论区

精彩推荐

A+B for Input-Output Practice (VII) （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【排队买票】 （C语言代码）

WU-输入输出格式练习 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

字符删除 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C二级辅导-统计字符 （C语言描述——用函数求解）

C二级辅导-温度转换（C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言训练-求素数问题（C语言代码）

　　评论区

【排队买票】（C语言代码）

WU-输入输出格式练习（C++代码）

字符删除（C语言代码）

C二级辅导-统计字符（C语言描述——用函数求解）