洛谷3172 [CQOI2015]选数

Luogu

BZOJ

分析

先做如下处理:

  • 若$K|L$,则把$L$变为$\frac{L}{K}$,否则把$L$变为$\left\lfloor\frac{L}{K}\right\rfloor+1$。
  • 把$H$变为$\left\lfloor\frac{H}{K}\right\rfloor$。

答案变为$[L,H]$间选数$N$次使得选出的数的$\gcd$为$1$的方案数。

设$f[i]$表示选数$N$次使得选出的数的公约数为$i$的方案数。

设$x$为$[L,H]$间$i$的倍数的个数,显然$f[i]=x^N-x$。

现在搞出了公约数为$i$的方案数,答案要求的是最大公约数为$1$的方案数。

大力容斥,将$f[i]$减去$f[2i],f[3i],...,f[ki]$即可。

注意,当$L=1$时所有的数都可以选$1$,此时$f[1]$要加$1$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;
const int MOD=1000000007;

int N,K,L,H;
int f[MAXN];

inline int FastPow(int a,int b) {
    int ans=1;
    while (b) {
        if (b&1) ans=1ll*ans*a%MOD;
        a=1ll*a*a%MOD,b>>=1;
    }
    return ans;
}

int main() {
    N=read(),K=read(),L=read(),H=read();
    L=L%K ? L/K+1 : L/K, H/=K;
    for (re int i=1;i<=H-L;++i) {
        int l=L%i ? L/i+1 : L/i, r=H/i;
        f[i]=(FastPow(r-l+1,N)-(r-l+1)+MOD)%MOD;
    }
    for (re int i=H-L;i;--i)
        for (re int j=i<<1;j<=H-L;j+=i)
            f[i]=(f[i]-f[j]+MOD)%MOD;
    if (L==1) f[1]=(f[1]+1)%MOD;
    printf("%d\n",f[1]);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 17 PM

发表评论