Plus and Multiply

  • Quiz
  • AC
  • 解説
    • 書き下してもパターンは見当たらないが、項のうちbが係数であるものは+bで作れると考えると、それ以外の項はaの累乗のみ
    • aの操作を先、bの操作を後としても作れる集合は同じ
  • ポイント
    • 操作に順番がつけられる

f:id:peroon:20210706160511p:plain

void solve(){
  ll N,a,b;
  cin>>N>>a>>b;

  if(a==1){
    N--;
    if(N%b==0){
      p_yes();
    }else{
      p_no();
    }
    return;
  }

  rep(i,inf){
    ll A = ll_pow(a,i);
    if(A>N)break;
    ll rest = N-A;
    if(rest%b==0){
      p_yes();return;
    }
  }
  p_no();
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}