CSP2022-T2（解密）

【题目来源】：http://oj.tfls.net/d/lnzt/p/14

 【分析】由题目可知：n=p×q,e×d=(p−1)(q−1)+1,化解可得：e×d=p×q-p-q+1+1=n-p-q+2，又从题目可知：m=n-e×d+2，合并可得，m=p+q。

【20分】枚举，时间复杂度O(n*k)   （实测40分）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main() {
 5     int k,m,i,n,d,e,p,q;
 6     cin>>k;
 7     while(k--){
 8         cin>>n>>d>>e;
 9         m=n-e*d+2; 
10         for(i=1;i<=n;i++){
11             p=i;   //枚举p值 
12             if(n%p==0){
13                 q=n/p;   //满足n=p*q 
14                 if(p+q==m){   //满足m=p+q
15                     cout<<p<<" "<<q<<endl;
16                     break;
17                 }     
18             }    
19         }
20         if(i>sqrt(n)) cout<<"NO"<<endl;    
21     }
22     return 0;
23 }

【60分】枚举p时，不需要从1到n，只需要到sqrt(n)。时间复杂度O(sqrt(n)*k)

//设n=36,则有
//1*36=36
//2*18=36
//3*12=36
//4*9=36
//6*6=36   p=sqrt(n)
//9*4=36   此时p,q出现重复

1 for(i=1;i<=sqrt(n);i++)

 【100分】数学问题。

方法一：一元二次方程。分析可得：n=p×q,m=p+q，那么很容易想到（我当然知道这句话很欠揍）一元二次方程中根与系数的关系x₁+x₂=-b/a,x₁*x₂=c/a，可以构建一元二次方程x²-(x₁+x₂)x+x₁*x₂=0，即x²-mx+n=0，p、q为方程的两个根。题目中要求p、q为正整数，可以在求出根后利用n=p×q,m=p+q反向验证p、q是否符合题意。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main() {
 5     long long k,m,n,d,e,p,q,det,s;
 6     cin>>k;
 7     while(k--) {
 8         cin>>n>>d>>e;
 9         m=n-d*e+2;
10         det=m*m-4*n;    //计算根的判别式△  ,注意此处需计算m*m，会超出int范围
11         if(det<0)     {  //△<0，方程没有实数根
12             cout<<"NO"<<endl;
13             continue;
14         }
15         p=(m+sqrt(det))/2;  //计算p、q，且p一定>=q
16         q=(m-sqrt(det))/2;
17         if(p>0&&q>0&&p*q==n&&p+q==m)   //反向验证p、q是否满足题意
18             cout<<q<<" "<<p<<endl;
19         else cout<<"NO"<<endl;
20     }
21     return 0;
22 }

方法二：二元一次方程组。分析可得：n=p×q,m=p+q，利用完全平方公式(p+q)²=p²+2pq+q²,(p-q)²=p²-2pq+q²,可以推出(p-q)²=(p+q)²-4pq=m²-4n，可得二元一次方程组：p-q=sqrt(m²-4n)  ①，p+q=m ②，①+②得：2p=sqrt(m²-4n)+m，解得：p=(sqrt(m²-4n)+m)/2，q=n/p。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main() {
 5     long long k,m,n,d,e,p,q,det,s;
 6     cin>>k;
 7     while(k--) {
 8         cin>>n>>d>>e;
 9         m=n-d*e+2;
10         p=(sqrt(m*m-4*n)+m)/2;  
11         q=n/p;
12         if(p>q) swap(p,q);
13         if(p>0&&q>0&&p*q==n&&p+q==m)   //反向验证p、q是否满足题意
14             cout<<p<<" "<<q<<endl;
15         else cout<<"NO"<<endl;
16     }
17     return 0;
18 }