斯德哥尔摩 的博客

斯德哥尔摩 的博客

P3172 [CQOI2015]选数

posted on 2018-05-13 20:43:42 | under 刷题 |

P3172 [CQOI2015]选数

题目要求:$\sum_{i=L}^{H}\sum_{j=L}^{H}[gcd(i,j)==k]$

第一个想法:莫比乌斯反演!

数据范围$H-L<=10^5$告诉我们这个方法可行。

但是会比较烦,这里提供一个比较简单的方法:递推+容斥。

设$f(i)$表示$gcd$为$i* k$的$(i,j)$个数。

首先我们可以缩小H和L,即同时除以k,令$r=(H-1)/k,l=L/k$,结果不变(为什么是$(H-1)/k$?因为我们只要用到$H-1$)

那么在$L$到$H$范围内$i* k$的倍数有$r/i-l/i$个,那么从其中选出n个数组成数对的个数有$(r/i-l/i)^n$个。

但是我们不能算所有数都一样的数对,因为我们把递推范围缩小到$H-L$(或者说$r-l$)的前提是找不到两个及以上的数满足$gcd==x$。

如果是所有数都一样的数对,依然可能超出我们枚举的$gcd$的范围。所以要减去一个$r/i-l/i$

然后找范围以内所有i的倍数j,去除掉所有$f[j]$就可以得到$f[i]$。

最后注意,如果k在$H$到$L$的范围里,答案要+1

附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
#define MOD 1000000007
using namespace std;
long long n,k,l,r,f[MAXN];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
long long mexp(long long a,long long b,long long c){//快速幂
    long long s=1;
    while(b){
        if(b&1)s=s*a%c;
        a=a*a%c;
        b>>=1;
    }
    return s;
}
int main(){
    long long s=0,h;
    n=read();k=read();l=read();r=read();
    if(l<=k&&k<=r)s=1;
    l--;l/=k;r/=k;h=r-l;//缩小范围
    for(long long i=h;i>=1;i--){
        long long x=l/i,y=r/i;
        f[i]=(mexp(y-x,n,MOD)-(y-x)+MOD)%MOD;//求gcd为i的倍数的数对的个数
        for(long long j=i<<1;j<=h;j+=i)f[i]=(f[i]-f[j]+MOD)%MOD;//gcd为i的数对的个数
    }
    printf("%lld\n",f[1]+s);
    return 0;
}