P6786 「SWTR-6」GCDs & LCMs

有意思的推式子题

一开始看到这个式子是不知所措的，推理出来的结论倒是挺有意思的，还是第一次遇到这样推理的。

一开始是打算直接枚举的，时间复杂度太高了，这个式子有什么意义呢？
x+y+gcd（x，y） = lcm（x，y）

x 等于 y时，显然不成立
当y>x时，这时候就需要猜了。x+y+gcd（x，y）一定小于3y ，而lcm又是y的整数倍，x不等于y
可以发现，x+y+gcd一定等于2y的时候才成立。

可以推出，y 等于 3*x/2 ；

这个题就很轻易就能解出来了，一个数字对应一块答案

#include<Reisentyan>

ll num[300200];
map<ll, ll>se;
map<ll, ll >ma;//最小值是i时，其答案是

int main()
{
	ll n = q_;
	ll maxx = 0;
	ffp(i, 1, n)
	{
		num[i] = q_;
		maxx = max(maxx, num[i]);
		se[num[i]]++;
	}

	sort(num + 1, num + 1 + n);
	ffp(i, 1, n)
	{
		if (se[num[i]] == 0) { continue; }
		if ((num[i] & 1) == 0)
		{
			ll sum = num[i]*se[num[i]];
			ll fre = num[i];
			se.erase(fre);
			while ((fre & 1) == 0 && se[fre * 3 / 2])
			{
				fre = fre * 3 / 2;
				sum += fre*se[fre];
				se.erase(fre);
			}
			ma[num[i]] = sum;
		}
		else
		{
			ma[num[i]] = num[i]*se[num[i]];
			se.erase(num[i]);
		}
	}
	for (auto e : ma)
	{
		maxx = max(e.second, maxx);
	}
	cout << maxx << endl;
	return 0;
}

还有就是题解中的一种解法