CSP-J2022 T2 解密

題面

思路

思路一：暴力枚舉（歪解）

時間複雜度 ，是以分數拿不全， 點逾時。

// Author: PanDaoxi
#include <bits/stdc++.h>
#define int long long
using namespace std;

int k, n, e, d, p, q;
bool flag;

signed main(){
  ios :: sync_with_stdio(false);
  
  cin >> k;
  while(k--){
    cin >> n >> e >> d;
    flag = false;
    
    for(int i=1; i<=n; i++){
      if(n % i) continue;
      p = i, q = n / i;
      
      if(e*d == n - q - p + 2){
        if(p > q) swap(p, q);
        cout << p << " " << q << endl;
        flag = true;
        break;
      }
    }
    
    if(!flag) cout << "NO" << endl;
  }
  
  return 0;
}      

思路二：數學（正解）

知識：

• 完全平方公式：
• 簡單的應用：

// Author: PanDaoxi
#include <bits/stdc++.h>
#define int long long
using namespace std;

int k, n, e, d, p, q, a, b;

signed main(){
  ios :: sync_with_stdio(false);

  cin >> k;
  while(k--){
    cin >> n >> e >> d;

        a = n + 2 - e*d; // a = p + q
    b = sqrt(a*a - 4*n); // b = p - q;
    p = (a + b) / 2;
    q = a - p;

    if(p*q == n){ // 相乘得原數
      if(p > q) swap(p, q);
      cout << p << " " << q << endl;
    }
    else{
      cout << "NO" << endl;
    }
  }

  return 0;
}