yukicoder : No.546 オンリー・ワン

今回はナンバーワンになれました。(でも初回ACのコードはちょっと怪しい)
https://yukicoder.me/problems/no/546

問題

N個の異なる整数C[i]が与えられる。
[L,R]の範囲の整数のうち、C[i]のうち1つだけで割り切れるものの数を求めよ。

解法

[L,R]の範囲ではxの倍数はfloor(R/x)-ceil((L-1)/x)個ある。

以下のdp(mask)を包除原理の要領で加減算していこう。
dp(mask)のうちmaskが1箇所だけビットが立っているものの和が解である。

f(mask) := maskで示すbitmaskでセットされたiに対応するC[i]の最小公倍数
dp(mask) := [L,R]のうちf(mask)の倍数であり、かつ他のf(mask')の倍数ではないもの

先にf(mask)を計算しておけば、maskとmask'を総当たりしてもO(4^N)なので間に合う。
maskとmask'が異なる場合でもf(mask)=f(mask')となる場合に注意。

int N;
ll L,H;
ll C[101];
ll dp[1<<10];
pair<ll,ll> P[1<<10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>H;
	FOR(i,N) cin>>C[i];
	
	for(int mask=0;mask<1<<N;mask++) {
		ll h = 1;
		FOR(i,N) if(mask&(1<<i)) {
			h*=C[i]/__gcd(h,C[i]);
			if(h>1LL<<30) break;
		}
		P[mask]=make_pair(h,__builtin_popcount(mask));
	}
	sort(P,P+(1<<N));
	
	ll ret=0;
	for(int mask=(1<<N)-1;mask>=0;mask--) {
		dp[mask]=H/P[mask].first-(L-1)/P[mask].first;
		for(int mask2=mask+1;mask2<(1<<N);mask2++) {
			if(P[mask2].first % P[mask].first == 0) {
				dp[mask] -= dp[mask2];
			}
		}
		if(P[mask].second==1) ret+=dp[mask];
	}
	cout<<ret<<endl;
}

まとめ

最初ちょっと怪しいコードで通ってしまったけど大丈夫だろうか。