杭电ACM1019超时

发布网友发布时间：2024-09-30 04:32

共2个回答

热心网友时间：2024-11-06 21:07

for (i=1;i<=a*b;i++)这样求时间复杂度太高。
思路一：假设n个数字为a1,a2,...,an，先求a1和a2的LCM（利用辗转相除来求GCD，再拿a1/gcd*a2），得到的LCM为lcm1，再求lcm1与a3的LCM，这样迭代求取。
思路二：求出每个数字的质因数和每个质因数的个数，记录每个质因数的最大个数，如质因数2的最大个数是p2，3的最大个数是p3，等等，那么最后的LCM等于2^p2 * 3^p3 * ...的乘积。
以上过程注意乘法溢出问题即可。

热心网友时间：2024-11-06 21:09

对付ACM就不要按常规思路来，无所不用其极才是硬道理，才能出灵感，怎么老有人发ACM的问题，没创新意识就不要去参加，就像小学初中高中就大把大把的奥赛，顶个毛用。