[CSP-J 2022] 解密

蒟蒻思路的来源

这道题CCF还是放了很多水分在里面；首先看数据范围：

以下记 $m=n-e\times d+2$

是不是很熟悉？是的，这题CCF贴心提示我们用韦达定理和求根公式；

思路分析

首先，对 $e_i\times d_i$进行化简：
$$\begin{gathered} e_i\times d_i=(p_i-1)(q_i-1)+1 \\ =p_i\times q_i-(p_i+q_i)+2 \\ =n_i-(p_i+q_i)+2 \end{gathered}$$
因此，移项可得：
{ p i + q i = n i + 2 − e i × d i = − b a p i × q i = n i = c a \left\{

\right. {pi​+qi​=ni​+2−ei​×di​=−ab​pi​×qi​=ni​=ac​​
我们可以构造方程：$a{x}^2+bx+c=0$

即：$x^2+(e_i\times d_i-n_i-2)x+n=0$

根据求根公式，有：$\Delta =b^2-4ac=(e_i\times d_i-n_i-2{)}^2-4\times 1\times n_i=(e_i\times d_i-n_i-2{)}^2-4\times n_i(\Delta \ge 0)$

所以，有：

$$q_i/p_i=\frac{-b\pm \sqrt{b^2-4ac}}{2a}=\frac{-(e_i\times d_i-n_i-2)\pm \sqrt{(e_i\times d_i-n_i-2{)}^2-4\times n_i}}{2}$$

最后输出即可；但是要注意$q_i{p}_i$均为整数！

AC Code

	#include
using namespace std;
long long k,n,e,d;
long long b,c,drt;
long long x,y;
int main(){
	scanf("%lld",&k);
	while(k--){
		scanf("%lld%lld%lld",&n,&e,&d);
		c=n;
		b=e*d-n-2;
		drt=b*b-c-c-c-c;
		if(drt<0){
			printf("NO\n");continue;
		}
		if(sqrt(drt)*sqrt(drt)!=drt){
			printf("NO\n");continue;
		}
		drt=sqrt(drt);
		if((-b+drt)%2==1){
			printf("NO\n");continue;
		}
		x=(-b+drt)/2;
		y=(-b-drt)/2;
		if(x<=0||y<=0){
			printf("NO\n");continue;
		}
		printf("%lld %lld\n",y,x);
	}
	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