大家好，今天我來解題[CSP-J 2022] 解密
題目來源鏈接

1.讀題

[CSP-J 2022] 解密（民間數(shù)據(jù)）

題目描述

給定一個正整數(shù) $k$，有 $k$ 次詢問，每次給定三個正整數(shù) $n_i,e_i,d_i$，求兩個正整數(shù) $p_i,q_i$，使 $n_i=p_i\times q_i$、$e_i\times d_i=(p_i?1)(q_i?1)+1$。

輸入格式

第一行一個正整數(shù) $k$，表示有 $k$ 次詢問。

接下來 $k$ 行，第 $i$ 行三個正整數(shù) $n_i,d_i,e_i$。

輸出格式

輸出 $k$ 行，每行兩個正整數(shù) $p_i,q_i$ 表示答案。

為使輸出統(tǒng)一，你應(yīng)當(dāng)保證 $p_i\le q_i$。

如果無解，請輸出 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。

【數(shù)據(jù)范圍】

以下記 $m=n?e\times d+2$。

保證對于 $100\%$ 的數(shù)據(jù)，$1\le k\le {10}^5$，對于任意的 $1\le i\le k$，$1\le n_i\le {10}^{18}$，$1\le e_i\times d_i\le {10}^{18}$
，$1\le m\le {10}^9$。

做法：

1.暴力窮舉(TLE)

經(jīng)過讀題，可知輸入一個整數(shù)$k$，$k$帶表詢問次數(shù)，應(yīng)有一層while 循環(huán)while (i--){}控制，循環(huán)內(nèi)輸入三個數(shù)$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循環(huán)窮舉，以下為了方便演示，用帶碼塊。

1.窮舉1（40分）

#include<bits/stdc++.h>
using namespace std;
int k,n,d,e;//其名即其意
int main ( )
{
    ios::sync_with_stdio(false);//關(guān)閉同步流（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;//不跳循環(huán)會出現(xiàn)多組答案
			}
		}
		if (key==0)//沒找到
			cout<<"NO"<<endl;//輸出NO
    }
    return 0;//結(jié)束程序
}

1.窮舉2（60分）

其實不然，細(xì)心可以讓人出先20分的差距

如上表，$10^9$int型可存儲2的31次方-1，也就是,$n\times m$遠(yuǎn)遠(yuǎn)大于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.數(shù)學(xué)思維（AC）

首先讓我們分解$(p_i?1)(q_i?1)+1$，解的$e_i\times d_i=(p_i?1)(q_i?1)+1=p_i{q}_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_i{q}_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_i{q}_i+q_i^2+p_i^2?2p_i{q}_i+q_i^2$，若在此基礎(chǔ)上，，可得$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;
    }
}

最后，一首小詩xian給大家

十年OJ一場空，不開long long 見祖宗。
閑來無事學(xué)數(shù)學(xué)，莫要考試看窮舉 。文章來源地址http://www.zghlxwxcb.cn/news/detail-718051.html

到了這里，關(guān)于[CSP-J 2022] 解密的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！