AtCoder Regular Contest 106 A - 106

問題について考えたこと

問題文へ

3+5=Nをを満たす正の整数の組（A,B）を求めます。

A、B共に正の整数であることから、0を含みません。累乗なのですべてを確認しても実効時間制限に間に合うと判断しました。

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  ll N;
  cin >> N;


  vector<ll> A;
  ll num = 3;
  while (num < N) {
    A.push_back(num);
    num *= 3;
  }
  vector<ll> B;
  num = 5;
  while (num < N) {
    B.push_back(num);
    num *= 5;
  }

  bool ok = false;
  pair<ll, ll> ans;
  rep(i, A.size()) {
    rep(j, B.size()) {
      if (N == A[i] + B[j]) {
        ok = true;
        ans.first = i + 1;
        ans.second = j + 1;
      }
    }
  }

  if (ok) {
    cout << ans.first << " " << ans.second << endl;
  } else {
    cout << -1 << endl;
  }

  
  return 0;
}