ARC106-Aの解答

AtCoder Regular Contest106-A 106の解答を書いていきます。問題はこちらから。

A - 106

Difficulty 180 （灰色）

問題

整数 n が与えられる。次式を満たす正の整数 a, b の組み合わせを求めよ。

3 ^ a + 5 ^ b = n

また、存在しない場合は -1 を出力します。

考察

まず、愚直に全探索ができるかどうか考えました。制約は

1 <= n <= 10^18

です。1 から 10^18 ですと、O(n)でも計算が間に合いませんが、今回は a, b が数字の肩に乗っているので a が小さくともすぐに 10^18 乗まで達します。具体的には

3^37 < 10 ^ 18 < 3^38
5^25 < 10 ^ 18 < 5^26

ですので、 37 * 25 = 925 回で全探索が完了します。全部調べて、見つからなければ -1 としましょう。

とはいうものの、37とか25という数字を求めるのも面倒くさいので、a = 1として、条件式が n を超えるまで b を増やしながら回しましょう。超えてしまったら、a = 2として同様に b を増やしていきましょう。

オーバーフローに関して補足します。最大ケースである n <= 10^18 にて、5*10^18 という数字がざっくりと考えた最大の数となります（実際には取りませんが）。long longの最大値は9*10*^18よりも大きいので、この型で宣言をしておけば、オーバーフローは発生しません。

実装

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;

int main()
{
   ll n;
   cin >> n;
   int a = 0;
   int b = 0;
   ll ca = 1;
   ll cb = 1;

   while (1)
   {
       ++a;
       ca *= 3;
       cb = 1;
       b = 0;
       while (1)
       {
           ++b;
           cb *= 5;
           ll s = ca + cb;
           if (s == n)
           {
               cout << a << " " << b << endl;
               return 0;
           }
           if (s > n) break;
       }
       if (ca > n) break;

   }
   cout << -1 << endl;
   return 0;
}

おわりに

C++にpowという関数がありますが、 a や b は1つずつ増やしていくので、while文で前状態を使いながら探索するのが効率よいと思います。powの内部がどうなっているのかは詳しくは知りませんが、、

あと、オーバーフローの対処が大変な言語もあるみたいですね。こういうとき、pythonの力を借りたくなりますね。この問題のように計算量が少ないなど、pythonで通せる問題はおとなしくそちらで書いた方が、試験中の解答時間を削減できるかもしれません。