【CodeAC 683解密 题解】CSP-J 2022真题

题目链接： 题解原链接

题目描述

给定一个正整数 k k k，有 k k k 次询问，每次给定三个正整数 n i , e i , d i n_i, e_i, d_i ni,ei,di，求两个正整数 p i , q i p_i, q_i pi,qi，使 n i = p i × q i n_i = p_i imes q_i ni=pi×qi、 e i × d i = ( p i − 1 ) ( q i − 1 ) + 1 e_i imes d_i = (p_i - 1)(q_i - 1) + 1 ei×di=(pi−1)(qi−1)+1。

输入格式

第一行一个正整数 k k k，表示有 k k k 次询问。 接下来 k k k 行，第 i i i 行三个正整数 n i , d i , e i n_i, d_i, e_i ni,di,ei。

输出格式

输出 k k k 行，每行两个正整数 p i , q i p_i, q_i pi,qi 表示答案。

为使输出统一，你应当保证 p i ≤ q i p_i leq q_i pi≤qi。

如果无解，请输出 NO。

解题思路

前置知识

韦达定理 在一元二次方程 a x 2 + b x + c = 0 ax^2+bx+c=0 ax2+bx+c=0中，两根 x 1 , x 2 x_1,x_2 x1,x2有如下关系： x 1 + x 2 = − b a x 1 ∗ x 2 = c a x_1 + x_2 = -frac{b}{a} \ x_1 * x_2 = frac{c}{a} x1+x2=−abx1∗x2=ac 求根公式 在一元二次方程 a x 2 + b x + c = 0 ax^2+bx+c=0 ax2+bx+c=0中，两根 x 1 , x 2 x_1,x_2 x1,x2的值为: x 1 , 2 = − b ± b 2 − 4 a c 2 x_{1,2} = frac{-bpm sqrt{b^2-4ac}}{2} x1,2=2−b±b2−4ac

公式推导

已知 e ∗ d = ( p − 1 ) ( q − 1 ) + 1 , n = p q e*d=(p-1)(q-1)+1, n=pq e∗d=(p−1)(q−1)+1,n=pq e d = ( p − 1 ) ( q − 1 ) + 1    ⟹    e d = p q − p − q + 2    ⟹    e d = n − p − q + 2    ⟹    p + q = n − e d + 2 设 m = n − e d + 2 ed = (p-1)(q-1)+1 \ implies ed = pq - p-q+2 \ implies ed = n - p - q + 2 \ implies p+q=n - ed +2 \ 设m=n-ed+2 ed=(p−1)(q−1)+1⟹ed=pq−p−q+2⟹ed=n−p−q+2⟹p+q=n−ed+2设m=n−ed+2 故 { p q = n p + q = m egin{equation} egin{cases} pq=n \ p+q=m end{cases} end{equation} { pq=np+q=m 由韦达定理的逆定理可得， p , q p,q p,q是 x 2 − m x + n = 0 x^2-mx+n=0 x2−mx+n=0的两根

带入求根公式得： p = m ± m 2 − 4 n 2 q = m ± m 2 + 4 n 2 p=frac{mpm sqrt{m^2-4n}}{2} \ q=frac{mpm sqrt{m^2+4n}}{2} p=2m±m2−4n q=2m±m2+4n 由题意 p , q p,q p,q为正整数,因此需要满足下列条件： m 2 − 4 n > 0 m 2 + 4 n 为正整数 m ± m 2 + 4 n 2 为正整数即 m ± m 2 + 4 n 为偶数 m^2-4n>0 \ sqrt{m^2+4n} 为正整数 \ frac{mpm sqrt{m^2+4n}}{2} 为正整数即 {mpm sqrt{m^2+4n}}为偶数 m2−4n>0m2+4n 为正整数2m±m2+4n 为正整数即m±m2+4n 为偶数 如果满足上述条件则有解，解为 p = m ± m 2 − 4 n 2 q = m ± m 2 + 4 n 2 p=frac{mpm sqrt{m^2-4n}}{2} \ q=frac{mpm sqrt{m^2+4n}}{2} p=2m±m2−4n q=2m±m2+4n 否则无解，输出NO

代码：

#include <iostream>
#include <cmath>
using namespace std;

typedef long long LL;

int main() {
          
   
    int k;
    LL n, e, d;
    scanf("%d", &k);
    while (k --) {
          
   
        scanf("%lld%lld%lld", &n, &d, &e);
        LL m = n - e * d + 2;
        LL delta = m * m - 4 * n;
        LL r = sqrt(delta);
        if (delta < 0 || r * r != delta || (m - r) % 2) puts("NO");        
        else printf("%lld %lld
", (m - r) / 2, (m + r) / 2);
    }
    
    
    return 0;
}