学步园

The Unsolvable Problem

给出n，求满足a+b=n,a和b最小公倍数的最大值是多少...

把n取半，看拆分的两半有木有公约数...

#include <cstdio>
#include <iostream>
using namespace std;
int gcd(int a,int b)
{
	return (b==0?a:gcd(b,a%b));
}
int main()
{
	int n,T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%lld",&n);
		__int64 k=n/2;
		__int64 s;
		while (gcd(k,(n-k))!=1) k--;
		s=k*(n-k);
		printf("%I64d\n",s);
	}
	return 0;
}