日々精進

aikoと旅行とプログラミング

【AOJ 2706】Let's Solve Geometric Problems

問題

Let's Solve Geometric Problems | Aizu Online Judge

方針

  • b進数k桁の値は以下のように表すことができる.
     {0.d_1 d_2 d_3 \cdots d_k= d_1 \times b^{-1} + d_2 \times b^{-2} + d_3 \times b^{-3}  \cdots  d_k \times b^{-k}}
  • 上の式を変換すると, {\frac{d_1 b^{k-1}+d_2 b^{k-2} \cdots d_k}{b^k}}となることがわかる.
  • 上記の式の形に変換したときのbが答え.

コード

#include <iostream>
#include <cmath>
#include <utility>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
 
signed main(){
  int p, q;
  int k;
  cin >> p >> q;
  k = __gcd(p, q);
  p /= k;
  q /= k;
   
  int q_ = q;
  vector<pii> ans;
  for(int i = 2 ; i <= sqrt(q) ; i++){
    if(q_%i == 0){
      pii p = make_pair(i, 1);
      q_ /= i;
      while(q_%i == 0){
        p.second++;
        q_ /= i;
      }
      ans.push_back(p);
    }
  }
 
  if(q_ > 1) ans.push_back(pii(q_, 1));
   
  int a = 1;
  for(int i = 0 ; i <(int) ans.size() ; i++){
    a *= ans[i].first;
  }
 
  cout << a << endl;
}