平方数问题分析

平方数

给出包含M个数字的列表，和列表中所有数字的所有质因数。求出最长的子列表，使得子列表中所有数字的乘积是一个完全平方数。

输入

输入文件包含多组测试数据。第一行包含两个整数N , M ( 1 <= N <= 30 , 1 <= M <= 30000 ). N 是质因数的个数。接下来一行有N个整数，给出所有的质因数。然后一行包含M个整数，给出列表。

输入文件结束于N = M = 0.

输出

对于每组数据，输出最长子列表的两个位置坐标l r。l是该子列表在列表中的起始位置，r是结束位置。如果多种情况都满足子列表长度最大，输出l最小的一个。如果不存在这样的子列表输出“None”。

样例输入

3 4
2 3 5
4 9 25 6
3 4
2 3 5
6 6 3 3
0 0

样例输出

1 3
1 4

 

 

算法分析：

      看到这个题目，可能更多的人会想到用循环2层循环来求解，里层循环求几个数相乘的结果，然后判断它是否平方数，记录并判断是否最大序列。不过如果这样来做，那么给的质因数那行好像作用就不大了，而且还面临着一个比较麻烦的问题，就是判断一个数是不是平方数。还有就是如果给出的数字都比较大的话，很容易就溢出。然后有的人可能会说，那我可以用数组来相乘的结果。如果真是这样，那我也无语了。

      其实这个题目出的稍微简单了写，主要是给出了质因数那行。如果将该行去掉，也许好多人更多的想到的就是上面的解法。不过既然给出来了，那么就可以想想他们究竟是干什么用的。

 

解题思路：

      我们知道一个数如果是平方数，那么一定可以分解成同一个数字相乘，由此可以想到该平方数完全分解质因数后所有的质因数一定都是偶数个。如果想通了这点，那么这道题就迎刃而解了，给的质因数这行就是为我们解决判断一个数是否是平方数提供了思路。将上述思路中判断平方数的方法改下，将求乘积改为判断所求的几个数所有相同质因数是否都为偶数即可。如果都是偶数，那么该乘积就是平方数，否则就不是。其他的思路都是一样的。

 

题目总结：

      关于这道题目，给我们的其实就是求平方数的一个新思路。通过该题目，我们在平时做题的时候一定要思路灵活些，不能总是按照常规的方法去解题，应该多想想，多转换思路去思考，也许会发现有许多更好的方法。

 

题目不难，懒得写程序了，呵呵。

评论

1 楼 knzeus 2008-11-12  

如果是非连续子序列也许就更好玩了。