【AOJ 2706】Let's Solve Geometric Problems

問題

Let's Solve Geometric Problems | Aizu Online Judge

方針

• 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;
}