[CSP-J 2022] 解密-Toy模板网

这篇具有很好参考价值的文章主要介绍了[CSP-J 2022] 解密。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

大家好，今天我来解题[CSP-J 2022] 解密
题目来源链接

1.读题

[CSP-J 2022] 解密（民间数据）

题目描述

给定一个正整数 $k$ ，有 $k$ 次询问，每次给定三个正整数 $n_i, e_i, d_i$ ，求两个正整数 $p_i, q_i$ ，使 $n_i = p_i \times q_i$ 、 $e_i \times d_i = (p_i - 1)(q_i - 1) + 1$ 。

输入格式

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

接下来 $k$ 行，第 $i$ 行三个正整数 $n_i, d_i, e_i$ 。

输出格式

输出 $k$ 行，每行两个正整数 $p_i, q_i$ 表示答案。

为使输出统一，你应当保证 $p_i \leq q_i$ 。

如果无解，请输出 NO。

样例 #1

样例输入 #1

样例输出 #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。

【数据范围】

以下记 $\times d + 2$ 。

保证对于 $100\%$ 的数据， $\leq k \leq {10}^5$ ，对于任意的 $\leq i \leq k$ ， $\leq n_i \leq {10}^{18}$ ， $\leq e_i \times d_i \leq {10}^{18}$
， $\leq m \leq {10}^9$ 。

测试点编号	$\leq$	$\leq$	$\leq$	特殊性质
$1$	$10^3$	$10^3$	$10^3$	保证有解
$2$	$10^3$	$10^3$	$10^3$	无
$3$	$10^3$	$10^9$	$6\times 10^4$	保证有解
$4$	$10^3$	$10^9$	$6\times 10^4$	无
$5$	$10^3$	$10^9$	$10^9$	保证有解
$6$	$10^3$	$10^9$	$10^9$	无
$7$	$10^5$	$10^{18}$	$10^9$	保证若有解则 $p = q$
$8$	$10^5$	$10^{18}$	$10^9$	保证有解
$9$	$10^5$	$10^{18}$	$10^9$	无
$10$	$10^5$	$10^{18}$	$10^9$	无

做法：

1.暴力穷举(TLE)

经过读题，可知输入一个整数 $k$ ， $k$ 带表询问次数，应有一层while 循环while (i--){}控制，循环内输入三个数 $n_i, e_i, d_i$ ，穷举 $p_i, q_i$ ,使 $p_i\times q_i=n_i$ 且 $e_i \times d_i = (p_i - 1)(q_i - 1) + 1$ ，所以此处用for循环穷举，以下为了方便演示，用带码块。

1.穷举1（40分）

#include<bits/stdc++.h>
using namespace std;
int k,n,d,e;//其名即其意
int main ( )
{
    ios::sync_with_stdio(false);//关闭同步流（cin,cout scanf化），可以省时间
    cin>>k;//输入k
    while (k--)//k次
    {
    	bool key=0;//控制NO与p,q输出
        cin>>n>>d>>e;//输入n,d,e
        for (int p=1;p*p<=n;p++)
        {
        	if ((p-1)*(n/p-1)+1==e*d)//满足上加粗部分
        	{
        		key=1;//找到了
        		cout<<p<<" "<<n/p<<endl;//输出
        		break;//不跳循环会出现多组答案
			}
		}
		if (key==0)//没找到
			cout<<"NO"<<endl;//输出NO
    }
    return 0;//结束程序
}

1.穷举2（60分）

其实不然，细心可以让人出先20分的差距

测试点编号	$\leq$	$\leq$	$\leq$	特殊性质
$5$	$10^3$	$10^9$	$10^9$	保证有解
$6$	$10^3$	$10^9$	$10^9$	无

如上表， $10^9$ int型可存储2的31次方-1，也就是 $2147483647，2.1\times10^9$ , $\times m$ 远远大于INT_MAX,故开long long。

#include<bits/stdc++.h>
using namespace std;
long long k,n,d,e;//开long lnog
int main ( )
{
    ios::sync_with_stdio(false);
    cin>>k;
    while (k--)
    {
    	bool key=0;
        cin>>n>>d>>e;
        for (int p=1;p*p<=n;p++)
        {
        	if ((p-1)*(n/p-1)+1==e*d)
        	{
        		key=1;
        		cout<<p<<" "<<n/p<<endl;
        		break;
			}
		}
		if (key==0)
			cout<<"NO"<<endl;
    }
    return 0;
}

十年OJ一场空，不开long long 见祖宗。

2.数学思维（AC）

首先让我们分解 $p_i - 1)(q_i - 1) + 1$ ，解的 $e_i \times d_i = (p_i - 1)(q_i - 1) + 1=p_iq_i-p_i-q_i+2$ 因为 $e_i \times d_i =(p_i - 1)(q_i - 1) + 1$ 且 $n_i=p_i \times q_i$ ，所以 $p_i + q_i=e_i \times d_i=p_iq_i-p_i-q_i+2=n_i-p_i-q_i+2$ ，所以$ $众所周知平方和公式$ (a+b)^2=a2+2ab+b^{2$，平方差公式$(a-b)}2，将二公式相加 $a^2+2ab+b^2+a^2-2ab+b^2=2a^2+2b^2$ ，将 $p_i,q_i$ 带入，为 $2p_i^2+2q_i^2=p_i^2+2p_iq_i+q_i^2+p_i^2-2p_iq_i+q_i^2$ ，若在此基础上，，可得 $p_i-q_i(p_i>q_i)$ ，那可解，

#include<bits/stdc++.h>
using namespace std;
long long k,n,d,e;
long long m; 
int main ( )
{
    ios::sync_with_stdio(false);
    cin>>k;
    while (k--)
    {
        cin>>e>>n>>d;
        m=e-n*d+2;
        double p=(m-1.0*sqrt(m*m-4*e))/2.0;
        long long p1=p;
        long long q=m-p;
        if (m*m-4*e<0||p1!=p||p1*q!=e)
            cout<<"NO"<<endl;
        else 
            cout<<p1<<" "<<q<<endl;
    }
}