Sqrt Approaching (数学推导+放缩)

原题题面

Given three positive integers $A,B,n$, where $n$ is NOT a perfect square number, you should find two positive integers $C,D$ satisfying $(BC-AD)(C-D\sqrt{n})<0$

输入格式

The first line contains one integer $A(1\le A<10^{99990}).$
The second line contains one integer $B(1\le B<10^{99990}).$
The third line contains one integer $n(2\le n\le 10^9).$
It is guaranteed that $n$ is NOT a perfect square number.

输出格式

The first line contains one integer $C(1\le C<10^{10^5}).$
The second line contains one integer $D(1\le D<10^{10^5}).$

输入样例

2
1
2

输出样例

3
2

题面分析

想了很久的数学题。
给定三个正整数$A,B,n$，保证$n$不是完全平方数，求一对正整数$C,D$使
$$(BC-AD)(C-D\sqrt{n})<0$$
成立。
保证有解，有多个时输出其中一组。
首先不难得到$min(\frac{A}{B},\sqrt{n})<\frac{C}{D}<max(\frac{A}{B},\sqrt{n})$
很容易就可以明白$C,D$有无穷多组解，证明略。
因此本题的上下界比较宽松。
假设$\frac{A}{B}<\sqrt{n}$，我们可以构造$\frac{C}{D}=\frac{Xn+D}{Bn+Y}(X\ge A)$，易知存在$C,D$使得$\frac{C}{D}>\frac{A}{B}$
故考虑如何构造使得$\frac{C}{D}<\sqrt{n}$
$\frac{C}{D}-\sqrt{n}$
$=\frac{Xn+D-\sqrt{n}(Bn+Y)}{Bn+Y}$
$=\frac{(Xn-\sqrt{n}Bn)+(D-\sqrt{n}Y)}{Bn+Y}<0$
不妨令$D=0$，即满足$(Xn-\sqrt{n}Bn-\sqrt{n}Y)<0$
即$(X\sqrt{n}-Bn-Y)<0$
等价于$(B\sqrt{n}(1-\sqrt{n})+(X-B)\sqrt{n}-Y)<0$
等价于$(B\sqrt{n}(1-\sqrt{n})-(X-B)(1-\sqrt{n})+(X-B-Y))<0$
那只需要$X-B-Y<=0$即可，不妨$X=A+B,Y=A$
得到$\frac{C}{D}=\frac{(A+B)n}{Bn+A}$
经验证，得到其为正确解。
$\frac{A}{B}>\sqrt{n}$时推导类似，这里不再赘述。

AC代码(1232ms)

import java.math.BigInteger;
import java.util.Scanner;
public class Main
{
	public static void main(String[] args)
	{
		Scanner input = new Scanner(System.in);
		BigInteger A = input.nextBigInteger();
		BigInteger B = input.nextBigInteger();
		BigInteger n = input.nextBigInteger();
		BigInteger C = n.multiply((A.add(B)));
		BigInteger D = n.multiply(B).add(A);
		System.out.println(C);
		System.out.println(D);
	}
}

后记

用Python写的话应该可以更快…Java真拉胯
DrGilbert 2020.10.25

本文地址：https://blog.csdn.net/oampamp1/article/details/109276824