AOJ 1106 - Factorization of Quadratic Formula

問題概要

a,b,cが与えられるので、
ax²+bx+c = (px+q)(rx+s)を満たすp,q,r,sを求めよ。
そのような組み合わせがない場合は、"Impossible"を出力する。

制約

• 0 < a ≤ 10000
• -10000 ≤ b ≤ 10000
• -10000 ≤ c ≤ 10000
• 0 < p
• 0 < r
• (r < p) or (p == r and s ≤ q)

解法

与えられた式を変形すると、
ax²+bx+c = (px+q)(rx+s) = prx²+(ps+qr)x+qs
となり、

• a = pr
• b = ps+qr
• c = qs

を満たすので、
まず、aを満たすp,rを全列挙し、次にcを満たすq,sを全列挙する。
後はそれらのp,q,r,sの組み合わせでbを満たすか調べる。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 10000
typedef pair<int,int> pii;
int a,b,c;
 
bool input(){
  cin >> a >> b >> c;
  return a;
}
 
int main(){
  while(input()){
    bool found = false;
    vector<pii> pr,qs;
    for(int p = 1 ; p <= a ; p++){
      int r = a/p;
      if(a % p != 0 || p < r) continue;
      pr.push_back(pii(p,r));
    }
    int cc = c < 0 ? -c : c;
    for(int q = -cc ; q <= cc ; q++){
      if(q == 0) continue;
      int s = 0;
      if(c < 0){
        if(q < 0 && abs(c) % abs(q) == 0){
          if(abs(c) % abs(q) == 0){
            s = abs(c)/abs(q);
          }
        }else{
          if(abs(c) % q == 0){
            s = abs(c)/q;
            s = -s;
          }
        }
      }else{
        if(q < 0){
          if(c % abs(q) == 0){
            s = c/abs(q);
            s = -s;
          }
        }else{
          if(c % q == 0){
            s = c/q;
          }
        }
      }
      if(s == 0) continue;
      qs.push_back(pii(q,s));
    }
    if(c == 0){
      for(int i = -MAX ; i <= MAX ; i++){
        qs.push_back(pii(0,i));
        qs.push_back(pii(i,0));
      }
    }
    for(int i = 0 ; i < (int)pr.size() ; i++){
      for(int j = 0 ; j < (int)qs.size() ; j++){
        int p = pr[i].first,r = pr[i].second;
        int q = qs[j].first,s = qs[j].second;
        if(p == r && q < s) continue;
        if(p*s+q*r == b){
          cout << p << " " << q << " " << r << " " << s << endl;
          found = true;
          goto END;
        }
      }
    }
    if(!found){
      cout << "Impossible" << endl;
    }
  END:;
  }
  return 0;
}