Facebook Hacker Cup 2011 Bonus Assignments

昔まったく分からなかった問題を解いてみた。

問題を要約すると、

『整数をN個選べ。ただし選ばれた整数は以下のすべての条件を満たす。

1. N個の整数の最小値は、[A, B]の間。

2. N個の整数の最大値は、[C, D]の間。

3. N個の整数をすべて割ることができる2以上の整数は存在しない。

N個の数の選び方のパターン数を求めよ。』

包除原理を使うと解けるが、よく見てみると

• square-freeではない（＝perfect squareで割れる）
• prime factorsの個数が偶数個
• prime factorsの個数が奇数個

でパターンが足されたり、引かれたり、結果に反映させなかったり、が決まるのでメビウス関数を使えばいいことが分かる。エラトステネスの篩を応用することで、n log (n) で[1, n]までのメビウス関数を計算することができる。（もっと速い方法があるかも）

以上をふまえて書いてみたソース。

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

const long long MOD = 1000000000+7;
int mu[1000000+1];
int pr[1000000+1];

void init() {
    REP (i, 1000000+1)
        mu[i] = pr[i] = 1;
    pr[0] = pr[1] = 0;

    for (int i = 0; i <= 1000000; i++) {
        if (!pr[i])
            continue;

        for (int j = i; j <= 1000000; j += i) {
            mu[j] *= -1;
            pr[j] = 0;
        }

        long long sq = (long long) i * i;
        for (long long j = sq; j <= 1000000; j += sq)
            mu[j] = 0;
    }
}

long long mpow(long long x, long long p) {
    long long ret = 1;

    while (p) {
        if (p & 1)
            ret = ret * x % MOD;
        x = x * x % MOD;
        p >>= 1;
    }
    return ret;
}

long long cnt(int n, int l, int r) {
    long long ret = 0;

    for (int i = 1; i <= r; i++) {
        int ll = (l+i-1) / i;
        int rr = r / i;

        if (rr >= ll) {
            ret += mu[i] * mpow(rr-ll+1, n);
            ret %= MOD;
        }
    }

    return ret;
}

long long solve() {
    int N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    
    long long ret = cnt(N, A, D) - cnt(N, A, C-1) - cnt(N, B+1, D) + cnt(N, B+1, C-1);
    ret %= MOD;
    if (ret < 0)
        ret += MOD;
    return ret;
}

int main() {
    init();

    int T;
    cin >> T;

    REP (i, T) {
        cout << "Case #" << (i+1) << ": ";
        cout << solve() << endl;
    }

    return 0;
}