ARC 106 | A - 106

問題

https://atcoder.jp/contests/arc106/tasks/arc106_a

考えたこと

Aは冪乗なので、1以上かつ$log_A(N)$以下になる。
同様にBも、1以上かつ$log_B(N)$以下になる。
AもBも非常に非常に小さくなるので全探索で解ける。

なおNがintの範囲を超えているのでlong longを使う。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  cin >> n;
  ld a = log(n) / log(3) + 1;
  ld b = log(n) / log(5) + 1;
  ll av = 3;
  for (int i = 1; i <= a; i++) {
    ll bv = 5;
    for (int j = 1; j <= b; j++) {
      if (av + bv == n) {
        cout << i << " " << j << endl;
        return 0;
      }
      bv *= 5;
    }
    av *= 3;
  }

  cout << -1 << endl;
}

底の変換式の $log_a(n) = \frac{log(n)}{log(a)}$ を使っている。少数誤差があることを考慮して+1をしている。

以下のようにa, bの最大値を求めてもいいかもしれない。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  cin >> n;
  ld ma = 1;
  ld mb = 1;
  ll a = 3;
  ll b = 5;
  while (a < n) {
    a *= 3;
    ma++;
  }
  while (b < n) {
    b *= 5;
    mb++;
  }
  a = 3;
  for (int i = 1; i <= ma; i++) {
    b = 5;
    for (int j = 1; j <= mb; j++) {
      if (a + b == n) {
        cout << i << " " << j << endl;
        return 0;
      }
      b *= 5;
    }
    a *= 3;
  }

  cout << -1 << endl;
}

参考

• 解説: https://atcoder.jp/contests/arc106/editorial/256