[BZOJ 3930] [CQOI 2015] 选数

题目链接

[BZOJ 3930] [CQOI 2015] 选数

题解

中档题。题意大概是求从L到H中取N个数使它们的最大公约数为K的选区方案数。
考虑原题让你求l-r中gcd(i,j)=k的个数。
等价于求l/k-r/k中gcd(i,j)=1的个数.
我们设d[i]表示l/k-r/k中gcd(i,j)=i的个数,
容斥一下即可.注意特判所有数都相等的情况。

代码

Time: 220ms
Memory: 2068kB
#include<iostream>
using namespace std;

const long long  MOD = 1e9 + 7;
const int  MAXN = 100050;

long long a[MAXN], N, K, L, H, l, r;

long long quick_power(long long a, long long b) {
    long long ans = 1;
    while (b) {
        if (b & 1)ans = ans * a%MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

int main() {
    cin >> N >> K >> L >> H;
    l = L / K, r = H / K;
    if (L % K)l++;
    for (int i = H - L; i; i--) {
        int ll = l / i, rr = r / i;
        if (l % i)ll++;
        if (l <= r) {
            a[i] = (quick_power(rr - ll + 1, N) - (rr - ll + 1)) % MOD;
            for (int j = i * 2; j <= H - L; j += i)a[i] = (a[i] - a[j]) % MOD;
        }
    }
    if (l == 1)a[1]++;
    cout << (a[1] + MOD) % MOD << endl;
    return 0;
}

标签: combinatorics

添加新评论