hdu 5947 数论

题意：

给定$a,b$，找出$x,y$，使得
$$\begin{gathered} x+y=a \\ lcm(x,y)=b \end{gathered}$$

Solution：

似乎有$lcm$，要么跟唯一分解有关系，要么跟$gcd$有关系，唯一分解可以枚举分配因子的幂，但是有$120000$组样例，时间复杂度不够。

对于$gcd(x,y)$，设$k_1,k_2$满足
$$\begin{gathered} gcd(x,y)\cdot k_1=x \\ gcd(x,y)\cdot k_2=y \end{gathered}$$
那么
$$x+y=gcd(x,y)\cdot (k_1+k_2)=a\text{\hspace{1em}(1)}$$

$$xy=gcd(x,y{)}^2\cdot k_1{k}_2\text{\hspace{1em}(2)}$$

由$(2)$
$$lcm(x,y)=\frac{xy}{gcd(x,y)}=gcd(x,y)\cdot k_1{k}_2=b\text{\hspace{1em}(3)}$$
由$(1)(3)$
$$\begin{gathered} k_1+k_2=\frac{a}{gcd(x,y)} \\ {k}_1{k}_2=\frac{b}{gcd(x,y)}\text{\hspace{1em}(4)} \end{gathered}$$
因为$k1,k2$是除了$gcd(x,y)$之外的因子，于是$k1,k2$一定没有重复因子，于是$gcd(k_1,k_2)=1$

存在一个结论

若$x,y$互质，那么$x+y$与$xy$互质，证明如下

由辗转相除$gcd(a,b)=gcd(b,a\%b)$
$$gcd(x,y)=gcd(x+y,x)=1$$
即$x+y,x$互质，同理对$gcd(y,x)$操作，可以得到$x+y,y$互质

那么$(x+y{)}^2,xy$一定互质，因为每个因子都不会重复，又$x+y$已经包含了$(x+y{)}^2$的所有素因子了，于是得到$x+y,xy$互质

利用这个结论，我们可以得到
$$gcd(\frac{a}{gcd(x,y)},\frac{b}{gcd(x,y)})=1$$
于是
$$gcd(a,b)=gcd(x,y)$$
这样就可以得到$gcd(x,y)$的值，代入方程组$(4)$得到一个二元一次方程，就可以解出$k_1,k_2$，从而得到$x,y$，注意解出来的$k_1,k_2$要是正整数

// #include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=1e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=998244353;

pair<ll,ll> solve(ll a,ll b)
{
    //解方程组xy=a,x+y=b
    pair<ll,ll>ret={-1,-1};
    if(b*b<4*a) return ret;
    double y=(b+sqrt(b*b-4*a))/2;
    if(fabs(y-floor(y))>1e-8) return ret;
    return make_pair(b-y,y);
}

ll a,b;

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>a>>b)
    {
        ll gcd=__gcd(a,b);
        auto tmp=solve(b/gcd,a/gcd);
        if(tmp.first==-1) printf("No Solution\n");
        else printf("%lld %lld\n",tmp.first*gcd,tmp.second*gcd);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35