BZOJ 3930 - [CQOI2015]选数

#数学 #数论 #递推 #GCD
Published on 2016-08-14

题目地址

描述

在 [l,r](1≤l≤r≤109)[l, r](1\le l\le r\le {10}^9) 内选出 n(1≤n≤109)n(1\le n\le {10}^9) 个数（可以重复），问所选的数的最大公约数恰好为 k(≤k≤109)k(\le k\le {10}^9) 的方案总数。
保证 r−l≤105r - l \le {10}^5。

分析

因为 r−l≤105r - l\le {10}^5，所以任意两个数 i,ji, j 的 gcd≤105\gcd \le {10}^5，为什么？
证明：假设 gcd(i,j)=g(i≥j)\gcd(i, j) = g(i\ge j)，将 i,ji,j 写成 i=g⋅x,j=g⋅yi = g \cdot x, j = g \cdot y，则 (x−y)>=1(x - y) >= 1，所以 g⋅(x−y)≥gg \cdot (x - y) \ge g 即 i−j≥gi - j\ge g，所以 g≤105g\le {10}^5。

另外，本题还可以使用莫比乌斯反演，不过时间很卡，详见Po姐的博客。

代码

//  Created by Sengxian on 8/14/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3930 递推
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100000 + 3, modu = 1000000007;
inline int mod_pow(ll a, int b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % modu;
        a = a * a % modu;
        b >>= 1;
    }
    return ans;
}
int n, K, l, r, f[maxn];

int main() {
    scanf("%d%d%d%d", &n, &K, &l, &r);
    l = ceil((double)l / K), r /= K;
    for (int i = maxn - 1; i >= 1; --i) {
        static int ll, rr;
        ll = ceil(double(l) / i), rr = r / i;
        if (rr - ll + 1 <= 0) {f[i] = 0; continue;}
        f[i] = (mod_pow(rr - ll + 1, n) - (rr - ll + 1) + modu) % modu;
        for (int j = i << 1; j < maxn; j += i) f[i] = (f[i] - f[j] + modu) % modu;
    }
    if (l == 1) f[1]++;
    printf("%d\n", f[1]); 
    return 0;
}
BZOJ 4652 - [Noi2016]循环之美