目录

• 题目
• • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
  • 提示
• 文字题解
• • 分析
  • 代码
• 视频题解

题目

题目描述

给定一个正整数 $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 \times q_i ni​=pi​×qi​、 e i × d i = ( p i − 1 ) ( q i − 1 ) + 1 e_i \times d_i = (p_i - 1)(q_i - 1) + 1 ei​×di​=(pi​−1)(qi​−1)+1。

输入格式

第一行一个正整数 $k$，表示有 $k$ 次询问。

接下来 $k$ 行，第 $i$ 行三个正整数 n i , d i , e i n_i, d_i, e_i ni​,di​,ei​。

输出格式

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

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

如果无解，请输出 NO。

样例 #1

样例输入 #1

10
770 77 5
633 1 211
545 1 499
683 3 227
858 3 257
723 37 13
572 26 11
867 17 17
829 3 263
528 4 109

样例输出 #1

2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88

提示

【样例 #2】

见附件中的 decode/decode2.in 与 decode/decode2.ans。

【样例 #3】

见附件中的 decode/decode3.in 与 decode/decode3.ans。

【样例 #4】

见附件中的 decode/decode4.in 与 decode/decode4.ans。

【数据范围】

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

保证对于 $100\%$ 的数据， 1 ≤ k ≤ 10 5 1 \leq k \leq {10}^5 1≤k≤105，对于任意的 $1\le i\le k$， 1 ≤ n i ≤ 10 18 1 \leq n_i \leq {10}^{18} 1≤ni​≤1018， 1 ≤ e i × d i ≤ 10 18 1 \leq e_i \times d_i \leq {10}^{18} 1≤ei​×di​≤1018
， 1 ≤ m ≤ 10 9 1 \leq m \leq {10}^9 1≤m≤109。

附件下载

文字题解

分析

看第二个式子。

$e\times d=(p-1)(q-1)+1$

化简得：$e\times d=p\times q-p-q+2$

回头看第一个式子：$n=p\times q$ 发现两个式子都有 $p\times q$，于是考虑消去 $p\times q$

用 $n-e\times d+2$，得 $e\times d-(p\times q-p-q+2)=p+q$，这样我们就得到了 $p+q$ 的值。

现在我们知道 $p\times q$，还知道 $p+q$，想要求 $p,q$，还需要知道 $p-q$。

这时就用到了初一数学知识：完全平方公式。

{ ( a + b ) 2 = a 2 + b 2 + 2 a b ( a − b ) 2 = a 2 + b 2 − 2 a b \begin{cases}(a+b)^2=a^2+b^2+2ab\\(a-b)^2=a^2+b^2-2ab\end{cases} {(a+b)2=a2+b2+2ab(a−b)2=a2+b2−2ab​

将上面两个式子相减会得到： ( a + b ) 2 − 4 a b = ( a − b ) 2 (a+b)^2-4ab=(a-b)^2 (a+b)2−4ab=(a−b)2

将 $p,q$ 代入，得 ( p + q ) 2 − 4 p q = ( p − q ) 2 (p+q)^2-4pq=(p-q)^2 (p+q)2−4pq=(p−q)2

所以 p − q = ( p + q ) 2 − 4 p q p-q=\sqrt {(p+q)^2-4pq} p−q=(p+q)2−4pq ​

现在知道了 $p+q$ 和 $p-q$，可以求出 $p,q$ 的值了。

• p = ( p + q ) + ( p − q ) 2 p=\dfrac{(p+q)+(p-q)}{2} p=2(p+q)+(p−q)​
• $p=(p+q)-p$

最后输出要先输出较小的，再输出较大的，用 $\min$ 和 $\max$ 函数就行。

代码

#include
using namespace std;
int k;//测试数据组数
int main()
{
//	freopen("decode.in","r",stdin);
//	freopen("decode.out","w",stdout);scanf("%d",&k);for(int i=1;i<=k;i++){long long n,e,d;scanf("%lld%lld%lld",&n,&d,&e);long long x=n-d*e+2;//x为 p+q 的值double r=sqrt((x*x-4*n)*1.0);//r为 p+q 的值if(long(r)!=r) printf("NO\n");//r是小数，则无解else{long long p=(x+r)/2;if(p!=(x+r)/2.0) printf("NO\n");//p是小数，则无解else printf("%lld %lld\n",min(p,x-p),max(p,x-p));//先输出较小的，再输出较大的}}return 0;
}

视频题解

[CSP-J 2022] 解密

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！