[ICPC2016Dalian Onsite]D. A Simple Math Problem 作者: rin 时间: October 19, 2016 分类: Algo **Time Limited:1 Sec Memory Limited: 64M** ###Description Given two positive integers $$a$$ and $$b$$, find suitable $$X$$ and $$Y$$ to meet the conditions: $$X+Y=a$$ $$Least Common Multiple(X,Y)=b$$ :hj-ovo: ###Input Input includes multiple sets of test data, Each test data occupies one line, including two positive integers $$a(1\leq a\leq 2*10^{4})$$, $$b(1\leq b\leq 10^{9})$$, and their meanings are shown in the description. Contains most of the 12W test cases. ###Output For each set of input data, output a line of two integers, representing $$X$$, $$Y$$. If you cannot find such $$X$$ and $$Y$$, output one line of "No Solution"(without quotation). ###Sample Input ``` 6 8 798 10780 ``` ###Sample Output ``` No Solution 308 490 ``` <!--more--> 设$$\gcd(X,Y)=c$$，有： ```katex \begin{array}{lll} X&=z_{1}\times c \\ Y&=z_{2}\times c \end{array} ``` （其中$$z_{1}, z_{2}$$互质） 根据原式1有： ```katex \begin{array}{lll} a&=X+Y \qquad (1)\\ &=(z_{1}+z_{2})\times c \qquad(2) \end{array} ``` 根据lcm的计算方法$$LCM(a,b)=\frac{a\times b}{gcd(a,b)}$$， ```katex \begin{array}{lll} b&=&LCM(X,Y)=\frac{X\times Y}{gcd(X,Y)} \\ b&=&\frac{(z_{1}\times c)\times (z_{2}\times c)}{c} \\ b&=&z_{1}\times z_{2}\times c \qquad(3) \end{array} ``` 由（2）（3）移项得： ```katex \begin{array}{lll} z_{1}+z_{2}=\frac{a}{c} \\ z_{1}\times z_{2}=\frac{b}{c} \end{array} ``` 可以求出$$z_{1}-z_{2}$$： ```math \begin{array}{lll} z_{1}-z_{2}&=&\sqrt{(z_{1}+z_{2})^{2}-4\times z_{1}\times z_{2}} \\ &=&\sqrt{(\frac{a}{c})^2-4\times \frac{b}{c}} \qquad(4) \end{array} ``` 从而得出 ```katex X-Y=(z_{1}-z_{2})\times c ``` 由（1）+（5）得： ```math X=\frac {(z_{1}-z_{2})\times c+a}{2} \qquad (5) ``` 最后 ```math Y=a-X ``` 发现（5）式中$$c$$未知，且$$z_{1}-z_{2}$$的计算也需要知道$$c$$。根据玄学可知$$z_{1}+z_{2}$$与$$z_{1}\times z_{2}$$互质，又有（2）（3）式： ```math \gcd[(z_{1}+z_{2})\times c,(z_{1}\times z_{2})\times c]=c ``` ```math \therefore c=\gcd(a,b) ``` --- 试证玄学 若$$z_{1}$$和$$z_{2}$$是质数，求证$$z_{1}+z_{2}$$ 与$$z_{1}\times z_{2}$$互质 证明： 设$$N=z_{1}+z_{2}, M=z_{1}\times z_{2}$$ 假设$$N$$与$$z_{1}$$不互质，则存在$$k=\gcd(z_{1},N)$$和整数$$A,B$$，使得 ```math \begin{array}{} kA=N \\ kB=z_{1} \end{array} ``` ```math \begin{array}{} \therefore z_{2}&=&N-z_{1} \\ &=&kA-kB \\ &=&k(A-B) \\ &\Rightarrow &k|z_{2} \end{array} ``` 与“$$z_{2}$$是质数”矛盾 $$\therefore z_{1}+z_{2}$$与$$z_{1}$$互质 同理，$$z_{1}+z_{2}$$与$$z_{2}$$互质 设$$F(x)=\gcd(x,z_{1}+z_{2})$$ 由上述结论有$$F(z_{1})=F(z_{2})=1$$ $$\because F(x)$$是积性函数 $$\therefore F(z_{1}\times z_{2})=F(z_{1})=F(z_{2})=1$$ $$\therefore \gcd(z_{1}+z_{2},z_{1}\times z_{2})=1$$，得证 标签: 数论