square869120Contest #2 : B - Division 2

全完はしたけど全体的に遅すぎた。
http://s8pc-2.contest.atcoder.jp/tasks/s8pc_2_b

問題

Q個の整数A[i]が与えられる。
1～Nの整数xのうち、「初期値xで初めて、A[0],A[1],A[2],...と順に見ていった際現在値がA[i]で割り切れるなら割る」という処理を行ったとき、最終的に1になるxはいくつあるか。

解法

Qは小さいので、各A[i]で割れる場合/割れない場合を2^Q通り総当たりし、条件を満たすuniqueな整数を列挙しよう。

割れるべきA[i]の積をpとする。
まずpが1～Nの間であるか判定しよう。
あとは実際pに対してA[i]で割れるか試してみる。

割れてはいけない部分で割れてしまった場合、そのpは解の候補から外す。

ll N;
int Q;
int A[25];
set<ll> S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,Q) cin>>A[i];
	
	ll ret=0;
	for(int mask=0;mask<1<<Q;mask++) {
		ll di=1;
		
		FOR(i,Q) if(mask&(1<<i)) di=min(di*A[i],1LL<<50);
		if(di>N) continue;
		ll tmp=di;
		FOR(i,Q) {
			if(mask&(1<<i)) {
				if(di%A[i]!=0) break;
				di/=A[i];
			}
			else {
				if(di%A[i]==0) break;
			}
		}
		if(i==Q) S.insert(tmp);
	}
	cout<<S.size()<<endl;
	
}

まとめ

Bで結構苦戦して、「これ難易度順じゃない？」と期待してしまった。