- Quiz
- https://codeforces.com/contest/1542/problem/B
- S={1}とする。Sの要素には「aをかける or bを足す」を無限回できて要素を増殖できる。nを作れるか判定せよ。制約は109
- AC
- 解説
- 書き下してもパターンは見当たらないが、項のうちbが係数であるものは+bで作れると考えると、それ以外の項はaの累乗のみ
- aの操作を先、bの操作を後としても作れる集合は同じ
- ポイント
- 操作に順番がつけられる
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; }