SRM491 Div2 Hard(1000) BottlesOnShelf

BottlesOnShelf
包除原理。複数のボールのどれかで壊れる瓶の本数を求めるのは難しいが、複数のボールのどれでも壊れる瓶はleftの最大値とrightの最小値の間でdamageの最小公倍数の倍数の瓶。

#include <vector>
using namespace std;

long long gcd(long long a,long long b)
    {long long t;if(a>b)t=a,a=b,b=t;while(a)t=a,a=b%a,b=t;return b;}
long long lcm(long long a,long long b){return a*b/gcd(a,b);}

class BottlesOnShelf{public:
int getNumBroken( int N, vector <int> left, vector <int> right, vector <int> damage )
{
    int n = (int)left.size();
    int ans = 0;

    for ( int i=1; i<1<<n; i++ )
    {
        int l = 1;
        int r = N;
        long long d = 1;
        int c = 0;
        for ( int j=0; j<n; j++ )
            if ( i>>j & 1 )
                l = max( l, left[j] ),
                r = min( r, right[j] ),
                d = lcm( d, damage[j] ),
                c++;

        if ( l <= r )
            ans += (c%2*2-1) * int( r/d - (l-1)/d );
    }

    return ans;
}};