【题解】高斯减法

题意

给你两个整数，让你将两个整数变为相等，其方法是每次可以选择一个数将其减去。初始为，每进行一次操作，的值加一。求最小操作次数，以及最终和的值。

题解

令和中，为较小值，若把和看作一个整体，即，若考虑进行了次操作，总的减少的数量就是。那么要求最后两个数字相等，所以即满足。但是由于和比较大，我们不可能去遍历的找到，那么考虑最终的结果为。由于一直在做减法操作，所以最终的结果肯定是小于等于的，那么我们就可以得到不等式。转化一下就变成了。又会有。所以就有。就能够大幅度减少能的范围，我们在的基础上向后找一个的结果即可。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long a,b;
        scanf("%lld%lld",&a,&b);
        if(a>b)
            swap(a,b);
        long long sum=2*b-2*a;
        long long c=a+b;
        long long n=sqrt(sum);
        for(long long i=n;i<=n+5;i++)
        {
            if((c-i*(i+1)/2)%2==0&&(c-i*(i+1)/2)/2<=a)
            {
                n=i;
                break;
            }
        }
        printf("%lld %lld\n",n,(a+b-n*(n+1)/2)/2);
    }
    return 0;
}