[CQOI2015]选数

题目描述

我们知道，从区间\([L,H]\)（\(L\)和\(H\)为整数）中选取\(N\)个整数，总共有\((H-L+1)^N\)种方案。

小\(z\)很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的\(N\)个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。

你的任务很简单，小\(z\)会告诉你一个整数\(K\)，你需要回答他最大公约数刚好为\(K\)的选取方案有多少个。由于方案数较大，你只需要输出其除以\(1000000007\)的余数即可。

输入输出格式

输入格式：

输入一行，包含\(4\)个空格分开的正整数，依次为\(N\)，\(K\)，\(L\)和\(H\)。

输出格式：

输出一个整数，为所求方案数。

说明

对于\(100\%\)的数据，\(1 \le N, K \le 10^9\)，\(1 \le L \le H \le 10^9\)，\(H-L \le10^5\)

暴力反演一波你会发现要求这个式子

\[\sum_{d=1}^{\lfloor\frac{r}{k}\rfloor}\mu(d)(\lfloor\frac{\lfloor\frac{r}{k}\rfloor}{d}\rfloor-\lfloor\frac{\lceil\frac{l}{k}\rceil-1}{d}\rfloor)
\]

需要使用杜教筛，不想学，发现还有一个神仙的\(DP\)

令\(r=\lfloor\frac{r}{k}\rfloor,l=\lceil\frac{l}{k}\rceil\)

问题等价于问互质的方案数

引理：区间\([l,r]\)任意两个不相等数的最大公约数的大小不会超过\(r-l\)

证明：取任意互质的数\(a,b\)，将它们同乘\(m\)，而\(r-l\)取最小值时\((b-a)\times m \ge m\)，得证

（证明是从别处抄的，说实话不太懂QAQ）

设\(dp_{i}\)代表以\(i\)为最大公约数的数量，且所选的数不全相等。

考虑\(g_i\)为\(i\)为约数的数量，同样也是所选的不全相等。

（不全相等是处于统计方便考虑）

显然

\[g_i=(\lfloor\frac{r}{i}\rfloor-\lfloor\frac{l-1}{i}\rfloor)^n-(\lfloor\frac{r}{i}\rfloor-\lfloor\frac{l-1}{i}\rfloor)
\]

根据容斥原理

\[dp_i=g_i-\sum_{i|d}^rdp_d
\]

注意要特判\(l=1\)，因为这个时候可以全相等

Code:

#include <cstdio>

#define ll long long

const int N=1e5+10;

const ll mod=1e9+7;

ll n,k,l,r;

ll dp[N];

ll quickpow(ll d,ll k)

{

    ll f=1;

    while(k)

    {

        if(k&1) f=f*d%mod;

        d=d*d%mod;

        k>>=1;

    }

    return f;

}

int main()

{

    scanf("%lld%lld%lld%lld",&n,&k,&l,&r);

    l=(l-1)/k+1,r=r/k;

    for(ll i=1;i<=r-l;i++)

    {

        ll cnt=(r/i-(l-1)/i);

        dp[i]=quickpow(cnt,n)-cnt;

    }

    for(ll i=r-l;i;i--)

        for(ll j=i<<1;j<=r-l;j+=i)

            (dp[i]-=dp[j])%=mod;

    printf("%lld\n",(dp[1]+(l==1)+mod)%mod);

    return 0;

}

2018.10.20

巴特西

洛谷 [CQOI2015]选数解题报告

[CQOI2015]选数

题目描述

输入输出格式

输入格式：

输出格式：

说明

最新文章

热门文章

巴特西

洛谷 [CQOI2015]选数 解题报告

[CQOI2015]选数

题目描述

输入输出格式

输入格式：

输出格式：

说明

最新文章

热门文章

洛谷 [CQOI2015]选数解题报告