刷题笔记：[CSP-J 2022 T2] 解密

老鹰爪子

闲话：由于不可抗力，CSP-J 2022 SD被ban了。
<hr/>题目描述简单粗暴，如图


一眼数学题
当然，也可以写暴力，但是只能得60pts。接下来主要讲一下本题公式是如何推出来的（为了便于理解，公式的推导过程用本题第一个样例：“770 77 5”来讲解）
<hr/>首先，由题意，得：
pq=770 ①
(p-1)(q-1)+1=385②
将②式去括号，得
pq-p-q+1+1=385
移项，得：
pq-(p+q)=383
带入①式，得
p+q=387③
推到这里，我注意到了数据范围：

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

也就是 p+q=m 嘛，证明了我们推到这里是正确的
联立①③式，得
pq=770
p+q=387
到这里，我们仅仅进行了最基本的推理
<hr/>不知道大家看到"pq""p+q"有没有想到了什么，学了一元二次方程的肯定都知道，这里科普一下：

如果一元二次方程 ax^2+bx+c=0 的两个根是 x_1,x_2 ,那么 x_1+x_2 =-\frac{b}{a},x_1x_2=\frac{c}{a}

不妨构造一个类似于ax^2+bx+c=0的方程
接下来， p=x_1 , q=x_2
则 x_1+x_2=387=-\frac{b}{a} ,得 b=-387a
同理得： c=770a
把这两个式子带入ax^2+bx+c=0，得：
ax^2-387ax+770a=0
提取公因式 a ，得：
a(x^2-387x+770)=0
显然， a\ne0 (因为分母不为0），只能 x^2-387x+770=0
再给没学过一元二次方程的同学科普一下：
对于类似于ax^2+bx+c=0的式子，可以使用求根公式解决， x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}
迁移运用一下，解出本题答案：
x=\frac{387\pm\sqrt{(-387)^2-4\times 770}}{2}
前面提到了，对于这个样例， m=n-e\times d +2=387 ， pq=770
所以，带入以上式子，得出最终公式：
x=\frac{m\pm\sqrt{m^2-4n}}{2}
到这里，推理基本结束
<hr/>那么对于NO的情况怎么办？
题目要求， p,q 必须是正整数
除了正整数，还有0，负数，小数除不尽的情况
对于0和小数除不尽，只需要将计算出来的 p,q 带入验算即可
对于负数，C++自带的sqrt负数时会Nan，而Nan在longlong中是0，故也可以参照0和小数除不尽的方案执行
到这里，讲解基本结束，代码显然：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
ll k;
ll n,d,e;
int main()
{
        scanf("%lld",&k);
        while(k--)
        {
                scanf("%lld%lld%lld",&n,&d,&e);
                ll m=n-e*d+2;
                long long sqr=sqrt(m*m-(4*n));
                ll ans1=(m-sqr)/2;
                ll ans2=(m+sqr)/2;
                if(ans1*ans2 == n && (ans1-1)*(ans2-1)+1 == e*d)
                {
                        cout<<ans1<<" "<<ans2<<endl;
                }
                else printf("NO\n");
        }
}

的做法

顶起顶起顶起