SRp1022 @ 2024-08-29 18:52:14
你应该换一个思路!!!
秒AC!!!
lcm(a, b) = a * b / gcd(a, b)
也就是说, a b = lcm(a, b) gcd(a, b)!!!(不信的话自己试试看)
所以, 在讲了一大堆废话之后, 最终的思路就是:
从x一直枚举到y(注意, 不要从1开始枚举, 否则可能会TLE), 再设一个变量a(为了方便叙述, 我们暂且先这么叫它) = x y / i(循环变量), 判断a i 是否等于x * y和gcd(a, i)是不是等于x, 如果都满足, ans++
这样子的话, 不用特判任何事(包括#9 x = y)就能轻松AC啦!!!
by lllyyyyyy @ 2024-09-20 19:59:56
woc 还真过了，大佬orz，原理是怎么回事呢，知道xy=gcd(x,y)lcm(x,y)后，后面的怎么理解呢
by SRp1022 @ 2024-09-22 16:52:48
@lllyyyyyy, 由于a b = gcd(a, b) lcm(a, b), 所以a = gcd(a, b) lcm(a, b) / b, 我们只用枚举b就可以了。在枚举的同时还要注意, gcd(a, b) lcm(a, b) / b不一定除得尽, 所以还要判断a b是否等于x(gcd(a,b))y(lcm(a, b)), 以及gcd(a, b)是否等于x。(不用判断lcm(a, b)是否等于y, 因为如果a b == x y, 又gcd(a, b) == x, a b == gcd(a, b) lcm(a, b), 所以a b == x lcm(a, b), lcm(a, b) == y)
by SRp1022 @ 2024-09-22 16:53:45
还有, 你是不是按照《深入浅出》这本书写的?
by Arthur_Coding @ 2024-09-29 21:30:08
感谢大佬，顺利解决困扰好久的问题！
by chiyuwang @ 2024-12-18 19:30:29
大佬牛orz