SRM 491 Div2 Hard BottlesOnShelf

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11008

１〜Nまでの間でleft[i]〜right[i]の間の数字の内、damage[i]で割り切れる数字を消去する。全部で消去される数はいくつか？

やりかた

包除原理。まずは1~Nの整数に中でdamage中の少なくとも一つでも割り切れる数字の個数を考える。この問題は各damageについてその範囲が決まっているだけなので、それらの区間のandの区間を考慮すればいいだけ。

以下ソース。

class BottlesOnShelf {
public:
  ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
  ll lcm(ll a, ll b){return a * b / gcd(a, b);}
  int getNumBroken(int N, vector <int> left, vector <int> right, vector <int> damage) {
    ll result = 0;
    int M = left.size();
    
    for(int S = 1; S < 1 << M; S++){
      ll LCM = 1;
      ll l = 0, r = INF;
      for(int i = 0; i < M; i++) if(S >> i & 1) {
	LCM = lcm(LCM, damage[i]);
	l = max(l, (ll)left[i]);
	r = min(r, (ll)right[i]);
      }
      
      ll a = (l <= r) ? r / LCM - (l - 1) / LCM : 0;
      result += (__builtin_popcount(S) % 2 == 1) ? a : -a;
    }
    return (int)result;
  }
};

スムーズにできてよかった。

前回解いたときの記事↓。今見ると図の意味がよくわからないが記念に残しておく。

Practice roomのいくつかの解答を参考にしました。

包除原理。damageの要素数をMとすると考慮すべき約数が2^M-1存在する。この集合を一つ取り出した時（例えばdamage[1], damage[3], damage[4]だとする）、それぞれが担当する区間（ここではleft[1]〜right[1]、left[3]〜right[3]、left[4]〜right[4]）のANDの区間についてのみ考慮の対象にすればいい。結局そうするともれなくかつダブりなく数えることができる。

下の図などを参考にして考える。

以下ソース。

class BottlesOnShelf {
public:
  int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
  }
  int getNumBroken(int N, vector <int> left, vector <int> right, vector <int> damage) {
    int ret = 0;
    int M = damage.size();
    for(int i = 1; i < 1 << M; i++){
      int num = __builtin_popcount(i);
      ll lcm = 1;
      ll l = 1, r = N;
      for(int j = 0; j < M; j++){
	if(i >> j & 1){
	  lcm = lcm / gcd(lcm, damage[j]) * damage[j];
	  l = max(l, (ll)left[j]);
	  r = min(r, (ll)right[j]);
	}
      }
      if(l <= r)
	if(num % 2 == 0) ret -= (r / lcm - (l - 1) / lcm);
	else ret += (r / lcm - (l - 1) / lcm);
    }
    return ret;
  }
};

いまいちよくわかってない。