x を1からmまで決め打ちし、x = (y+a)^n を確認します。 ただし、このアルゴリズムでは、O(m)となり、実装次第では時間切れになる恐れがあります。
x の全ての桁の数字の和yは、xを10で割った余り、つまり下１桁の数字を加算し、10で割ることで下１桁を削除する、操作を繰り返すことで得られます。
y を決め打ちして、x=(y+a)^nを満たすものの個数を数えます。 yの最大値が小さいので、高速に答えを求めることができます。
参考文献：4つの言語で解ける 実践プログラミング問題集