まず、答えは必ず oo...oxx...x という形になります。
理由: \(N^k\) は今回の問題の制約上 (\(1 \le N\)) で \(p<q\) ならば \(N^p \le N^q\) となる。

次に、今回の問題の最大ケースを考察します。
\(N=10^9,M=10^5\) のとき、 \(N^k=(10^9)^{100000}\) と、 \(N^k\) の値が単純に扱うことのできない大きさになってしまいます。なので、単純に \(N^k\) の計算を行うのではなく何らかの工夫が必要となります。

ここで、先ほど述べた答えが oo...oxx...x の形になるという性質が生かされます。
ある時点で \(N^k > 10^9\) となれば、その先は特に計算をしなくとも x をつけてよいです。

なお、 \(N^k\) の値は \(k=1,2,...\) と\(k\) を \(1\) つ進めるごとに \(N\) 倍することで求めることができます。 また、 \(N^k \le 10^9\) のとき \(N^{(k+1)} \le 10^{18}\) なので、 long long 型のような \(64\)bit 符号付き整数があれば事足ります。(逆に、 unsigned int 型のような \(32\)bit 符号付き整数では(特別な工夫などをしない限り)桁が足りなくなります。)

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n,m;
  cin >> n >> m;
  long long val=1;
  for(int i=1;i<=m;i++){
    if(val>1000000000){
      cout << "x";
      continue;
    }
    val*=n;
    if(val>1000000000){cout << "x";}
    else{cout << "o";}
  }
  cout << "\n";
  return 0;
}