POJ 2773 Happy 2006

問題

自然数m, Kが与えられる。mと互いに素なK番目の自然数を返せ。

やりかた

逐一調べると当然間に合わない。ここは二分探索+包除原理。まず二分探索で解の候補を上げ、その解の候補に対して、それ以下の自然数でかつmと互いに素なものの個数を計算し、その大小で探索範囲をせばめる。
ある自然数x以下の自然数でmと互いに素な自然数の数を調べるには、まずmを素因数分解し、mの素因数を列挙する。ここから包除原理によってx以下の自然数のうちmの素因数を少なくとも１つ持つ自然数の数を求めることができる。互いに素な数はこの余事象になる。

以下ソース。

vector<int> fa(int n){
  set<int> r;
  for(int i = 2; i * i <= n; i++){
    while(n % i == 0){
      r.insert(i);
      n /= i;
    }
  }
  if(n != 1) r.insert(n);
  return vector<int>(ALL(r));
}

ll relative_prime(ll x, const vector<int> &pr){
  int N = pr.size();
  ll ret = 0; //x以下の自然数でmの素因数を少なくとも一つ持つ自然数の数
  for(int S = 1; S < 1 << N; S++){
    ll a = 1;
    for(int i = 0; i < N; i++)
      if(S >> i & 1) a *= pr[i];
    int bit = __builtin_popcount(S);
    if(bit & 1) ret += (x / a);
    else ret -= (x / a);
  }
  return x - ret; //互いに素な個数
}

int main(){
  ll m, K;
  while(cin >> m >> K){
    vector<int> pf = fa(m);
    
    ll ub = LLINF, lb = 0LL;
    while(lb < ub - 1){
      ll mid = (ub + lb) / 2;
      ll rp = relative_prime(mid, pf);
      if(rp >= K) ub = mid;
      else lb = mid;
    }
    cout << ub << endl;
  }
  return 0;
}