Niuke monthly race 31 minus integer

F

The question ：
Just give you a number n, Then subtract... In turn 1,2,3,… If it happens to be reduced to 0 Quit , If not enough, add n, from 1 Begin to reduce , I asked you how many times to repeat it, plus n This operation . Of course, it's an operation at the beginning . If there is no solution, output impossible.

reflection ：
At first, I felt like a direct simulation after reading this topic , See when you can quit at least , But it will definitely jam you . Then I feel that there is no solution , In fact, after careful consideration . When we reduce to b, Now there are still a,a Not enough to reduce b Then add n, After this operation, the rest will become 2a,3a…, So now is to ask you , How many? a-b==0. This is not obvious , Because it doesn't have to be added b This number , In fact, in the process of subtraction . As long as we reach xa%b==0 It must be equal to 0 了 . So it's asking for a and b The least common multiple of , Then divide by a, See how many you want a That's enough .
In fact, this topic , For the number of operations , Often take the HKCEE gcd The nature of the matter .

Code ：

int T,n,m,k;
int va[N];

signed main()
{
    
	IOS;
	cin>>T;
	while(T--)
	{
    
		cin>>n;
		int l = 1,r = n;
		while(l<r)
		{
    
			int mid = l+r+1>>1;
			if(mid*(mid+1)/2<=n) l = mid;
			else r = mid-1;
		}
		int a = n-l*(l+1)/2,b = l+1;
		if(a==0) // Pay attention to the special judgment here , Otherwise, division appears below 0 The situation of .
		{
    
			cout<<1<<"\n";
			continue;
		}
		int now = a*b/__gcd(a,b)/a;
		cout<<now<<"\n";
	}
	return 0;
}

summary ：
Accumulate more experience .