COLOCON 2018 C- すぬけそだて――ごはん――

• 問題

問題概要

自然数A,Bが与えられる。
A <= m <= Bなる自然数を選んだ全てが互いに素でなければならないという制約のもと非負整数個選ぶとき、選び方は何通りか。
1 <= A <= B <= 10¹⁸
B - A <= 35

解法

全探索して間に合う。その理由は解説参照。
特に6の倍数、その他の2の倍数、3の倍数で分けたりしなくても
全探索の過程で枝が切られるため単純に実装すれば良い。

別解としてA <= m,n <= Bが1でないgcdを持つとき制約から35以下の素数になるため、
prime[11] = {2,3,5,7,11,13,17,19,23,29,31}としてどれを素因数に持つかを11bitで持ち、DPしても良い。
dp[0] = 1
for(m:A<=m<=B)
for(bit:1<<11)
if(mがbitの素因数を持っていない) dp[bitにmを入れた時の次の状態] += dp[bit]
みたいな感じ。O(N*2¹¹)。

メモ

反省オブザイヤー。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 100005, MAX_C = 30;
const ll lmod = 1e9+7;

ll gcd(ll a,ll b){
    //  a >= b
    if(a<b) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}

ll solve(ll a,ll b,vector<ll> &vec){
  if(a>b) return 1LL;
  ll res = solve(a+1,b,vec);
  bool ok = true;
  for(auto c:vec){
    if(gcd(a,c)!=1LL){
      ok=false;
      break;
    }
  }
  if(ok){
    vec.pb(a);
    res += solve(a+1,b,vec);
    vec.pop_back();
  }
  return res;
}

int main(){
    ll A,B; cin >> A >> B ;
  vector<ll> vec;
  cout << solve(A,B,vec) << endl;
  return 0;
}