[CSP-J 2022 T2]解密题解

这题可以使用暴力求解，但是因为n的值过大，所以即使拥有单$O(k\sqrt{n})$的时间复杂度也只能获得60分，这道题的答案其实是数学的$O(k)$解，推导过程如下

$$∵(p-1)(q-1)+1=ed \newline∴pq-p-q+1+1=ed \newline∵pq=n \newline∴ed = n - p-q+2 \newline∴p+q=n-ed+2=m \newline∴(p+q)^2=m^2 \newline∴p^2+2pq+q^2=m^2 \newline∴m = \sqrt{(p+q)^2} = p+q \newline∴p^2-2pq+q^2=m^2-4pq \newline∴(p-q)^2=m^2-4pq \newline设c=p-q \newline∴c = \sqrt{m^2-4pq}=\sqrt{m^2-4n}=p-q(m^2-4pq,m^2-4n≥0) \newline∴m+c=2p(p为正整数,所以m+c为偶数) \newline∴q=m-(m+c)/2$$

答案就是先输出p、q中的较小值，再输出较大值
可以先写一下，实在写不出来再看代码吧!
$------------------------------------------$

#include<bits/stdc++.h>
using namespace std;
using ll = long long; // 因为数值较大，必须使用long long存储
int k;
signed main(){ // signed是个人习惯，和int没有区别
    cin >> k;
    while(k--){
        ll n, e, d;
        cin >> n >> e >> d;
        ll m = n - e * d + 2; // 得出推导公式的第5行中的m,也是p+q的值
        if (m * m - 4 * n < 0){ // 被开方数不能小于0
            cout << "NO\n";
            continue;
        }
        ll c = sqrt(m * m - 4 * n); // 得出p-q的值
        if ((m + c) % 2 != 0){ // p为正整数
            cout << "NO\n";
            continue;
        }   
        ll p = (m + c) / 2;
        ll q = m - p;
        cout << min(p, q) << ' ' << max(p, q) << endl; // 从小到大写
    }
    return 0;
}