编程论坛 » C语言论坛 » 平方数问题，高手低手随便看看，练练。。。。俺不懂

寒秋 发表于 2008-7-11 15:39

平方数问题，高手低手随便看看，练练。。。。俺不懂

给出包含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
谁会啊,而且还有时间限制的啊[tk10]

卧龙孔明 发表于 2008-7-11 18:00

给个OJ 吧，否则那些限制我不清楚

寒秋 发表于 2008-7-12 00:14

我不懂才问的。。。。。[tk05]

卧龙孔明 发表于 2008-7-12 07:58

[quote][bo][un]寒秋[/un] 在 2008-7-12 00:14 的发言：[/bo]

我不懂才问的。。。。。[tk05] [/quote]



我要帮你啊，你不明白我的意思？
我的意思是让你告诉它的测评地点，online judege的位置，或者你告诉我这个题的具体限制，我好帮你解答。

blackfail 发表于 2008-7-12 10:23

具体限制就是一个包含m个整数的数组求它的每一个元素的质因数的个数，然后求其中的拥有对多质因数的个数的元素的列表，我不明白如何才能使它的所有数的乘积是一个平方数呢？万一要不是？还需要改改？？

liangjian0 发表于 2008-7-12 10:28

[tk06] [tk06] 好深奥啊 我完全不明白












[img]http://www.cghp.net/images/DZ/sigline.gif[/img]
[url=http://www.sluke.cn/files/article/html/4/4910/]盗墓笔记[/url]

卧龙孔明 发表于 2008-7-12 12:14

[quote][bo][un]blackfail[/un] 在 2008-7-12 10:23 的发言：[/bo]

具体限制就是一个包含m个整数的数组求它的每一个元素的质因数的个数，然后求其中的拥有对多质因数的个数的元素的列表，我不明白如何才能使它的所有数的乘积是一个平方数呢？万一要不是？还需要改改？？ [/quote]


时间限制....?

[[it] 本帖最后由 卧龙孔明 于 2008-7-12 23:38 编辑 [/it]]

寒秋 发表于 2008-7-13 00:19

http://acm.fzu.edu.cn/problem.php?pid=1400
知道告诉我
[tk05]

leeco 发表于 2008-7-13 12:52

我貌似想到了一个O(MlogM)的算法，先试试

查看完整版本: 平方数问题，高手低手随便看看，练练。。。。俺不懂