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した。