kmjp's blog

競技プログラミング参加記です

AtCoder ABC #195 (パナソニックプログラミングコンテスト) : F - Coprime Present

Bで2WAした時点でダメダメ。
https://atcoder.jp/contests/abc195/tasks/abc195_f

問題

整数A以上B以下の整数の集合のうち、互いに素でない対がないものは何通りか。
なお、B-Aは72以下である。

解法

互いに素でない対があるとすると、その公約数は72以下である。
そこで72以下の素数20通りについて、その素数の倍数を含むかどうかを2^20通り状態としてもち、A~Bを順次集合に加えるか加えないか判定していこう。

ll A,B;

const int prime_max = 72;
vector<int> prime;
int NP,divp[prime_max];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

ll dp[1<<20];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	dp[0]=1;
	cprime();
	
	for(ll a=A;a<=B;a++) {
		int nmask=0;
		FOR(j,NP) if(a%prime[j]==0) nmask|=1<<j;
		for(int mask=(1<<20)-1;mask>=0;mask--) {
			if((mask&nmask)==0) dp[mask|nmask]+=dp[mask];
		}
	}
	
	ll ret=0;
	FOR(i,1<<20) ret+=dp[i];
	
	cout<<ret<<endl;
}

まとめ

最初枝刈り探索しようとしたらTLEした。