ARCあたりに出そう?
https://yukicoder.me/problems/no/1330
問題
N個の正整数A[i]と、正整数M、素数Pが与えられる。
変数x=1に対し、以下のいずれかを行う。
- xがPの倍数ならPで割る
- そうでないとき、1つA[i]を選んでxに掛ける
xがM以上になるのにかかる処理回数は何回か。
解法
xがMに到達にする最後の1手は最大のA[i]を掛ければよいので、それまでの手数を考える。
A[i]=P^a*Q (QはPを素因数に含まない)とすると、A[i]を掛けてxがMに到達しない場合、結局(a+1)手かけてQを掛けるのと同じ。
そこで
f(a+1) := A[i]のうちP^a*Qと表現できるもののQの最大値
とする。
コスト(a+1)でxにQを掛けられることになるので、あとはDPで手数に対し構築できるxの最大値を求めよう。
int N,M,P; int A[202020],B[202020]; int C[61]; ll dp[1000]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>P; int ma=0; FOR(i,N) { cin>>A[i]; ma=max(ma,A[i]); x=1; while(A[i]%P==0) A[i]/=P, x++; C[x]=max(C[x],A[i]); } dp[0]=1; FOR(i,900) { if(1LL*dp[i]*ma>M) { cout<<i+1<<endl; return; } for(j=1;j<=31;j++) dp[i+j]=max(dp[i+j],dp[i]*C[j]); } cout<<-1<<endl; }
まとめ
Pが素数じゃないと難易度どれぐらい変わるかな。