NEFU-1221 人见人爱GCD

Description

x+y=a,lcm(x,y)=b;已知a和b求解 x^2+y^2

Input

多组数据输入。 第一行一个t表示a,b数对的数量。 接下来t行2个数表示a,b T<=100000 a,b<10^9;

Output

每组样例输出t行每行一个数表示\(\)x^2+y^2[\latex];

分析

这个题比较巧妙，从数据范围来看显然不能够遍历计算出x，y后输出

进行一些数学运算后不难发现

$$a^2=x^2+y^2+2*x*y$$

$$x*y=gcd(x,y)*lcm(x,y)=gcd(x,y)*b$$

至此，也即我们需要化简gcd(x,y)，找出其与a,b之间的关系

不妨设$$m=gcd(x,y)$$则$$x=m*k1,y=m*k2$$

则得$$a=x+y=m*(k1+k2)$$ $$b=\frac{x*y}{gcd(x,y)}=\frac{x*y}{m}=k1*k2*m$$

自然$$gcd(a,b)=gcd( m*(k1+k2), k1*k2*m)=m*gcd(k1+k2,k1*k2)$$

又因为k1与k2互质故可得 $$gcd(a,b)=m=gcd(x,y)$$

Accepted Code

#include <bits/stdc++.h>
using namespace std;
long long rem;
long long gcd(long long a, long long b)
{
    if (a < b)
    {
        swap(a, b);
    }
    rem=0;
    while (b > 0)
    {
        rem = a % b;
        a = b;
        b = rem;
    }
    return a;
}
int main()
{
    int t;
    while (cin >> t)
    {
        while (t--)
        {
            long long a, b;
            scanf("%lld %lld",&a,&b);
            long long tmp=gcd(a,b);
            printf("%lld\n",a * a - 2 * b * tmp);
        }
    }
    return 0;
}

解后反思

数学还是重要啊