bzoj3930 [CQOI2015]选数（反演||容斥原理）

题目链接

分析：

自己YY的解法：

gcd=k g c d = k ，那么我们就可以把选出的数都分解成 (k∗a0,k∗a1,...,k∗an) ( k ∗ a 0 , k ∗ a 1 , . . . , k ∗ a n )

那么 gcd(a0,a1,...,an)=1 g c d ( a 0 , a 1 , . . . , a n ) = 1 ，其中一定能找到两个数满足 gcd(ai,aj)=1 g c d ( a i , a j ) = 1 ，其余数字可以任意选择

设 [l∗k,r∗k] [ l ∗ k , r ∗ k ] 包含在 [L,R] [ L , R ] 内且 [l,r] [ l , r ] 尽量大，那么 ai a i 的范围就是 [l,r] [ l , r ]

ans=(∑i=lr∑j=lr[gcd(i,j)=1]−1)∗(r−l+1)k−2 a n s = ( ∑ i = l r ∑ j = l r [ g c d ( i , j ) = 1 ] − 1 ) ∗ ( r − l + 1 ) k − 2

对于 ∑ni=1∑nj=1[gcd(i,j)=1]=2∗∑ni=1ϕ(i) ∑ i = 1 n ∑ j = 1 n [ g c d ( i , j ) = 1 ] = 2 ∗ ∑ i = 1 n ϕ ( i )

S(n)=∑ni=1ϕ(i)=∑ni=1(i−∑d|i,d<iϕ(d))=n(n+1)2−∑ni=2S(ni) S ( n ) = ∑ i = 1 n ϕ ( i ) = ∑ i = 1 n ( i − ∑ d | i , d < i ϕ ( d ) ) = n ( n + 1 ) 2 − ∑ i = 2 n S ( n i )

然而T掉了。。。

反演正解：

%%%PoPoQQQ

我化出来的式子是这样的：

∑ni=1μ(i)=S(n)=1−∑ni=2μ(ni) ∑ i = 1 n μ ( i ) = S ( n ) = 1 − ∑ i = 2 n μ ( n i )

用这个式子计算μ的前缀和也是可以的

tip

一开始还是T，时间卡的太紧

if(n/i-) ans-=(Sum(last)-Sum(i-))*(n/i-);
           

加了一个小特判，时间就减少了一多半：4000ms

#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#define ll long long

using namespace std;

const int INF=e9+;
const int N=e7+;
const ll p=e9+;
ll n,m,L,R;
int mu[N],sshu[N],tot=;
bool no[N];
map<int,ll> mp;

void prepare() {
    mu[]=;
    for (int i=;i<N;i++) {
        if (!no[i]) {
            sshu[++tot]=i;
            mu[i]=-;
        }
        for (int j=;j<=tot&&sshu[j]*i<N;j++) {
            no[sshu[j]*i]=;
            if (i%sshu[j]==) {
                mu[i*sshu[j]]=;
                break;
            }
            mu[i*sshu[j]]=-mu[i];
        }
    }
    for (int i=;i<N;i++) mu[i]=mu[i-]+mu[i];
}

ll KSM(ll a,ll b) {
    ll t=;
    while (b) {
        if (b&) t=(t*a)%p;
        b>>=;
        a=(a*a)%p;
    }
    return t%p;
}

ll Sum(int n) {
    if (n<N) return mu[n];
    if (mp.find(n)!=mp.end()) return mp[n];
    ll ans=,last;
    for (ll i=;i<=n;i=last+) {
        last=n/(n/i);
        if(n/i-) ans-=(Sum(last)-Sum(i-))*(n/i-);
    }
    mp[n]=ans;
    return ans;
}

ll solve() {
    ll last,ans=;
    for (ll i=;i<=R;i=last+) {
        last=min(R/(R/i),L/i?(L/(L/i)):INF);
        ans+=(Sum(last)-Sum(i-))*KSM(R/i-L/i,n);
        ans%=p;
    }
    return (ans%p+p)%p;
}

int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&L,&R);
    L=(L-)/m; R=R/m;
    prepare();
    printf("%lld",solve());
}
           

当然dada们还有其他解法

容斥：

YJQQQAQ

我们用 f[i] f [ i ] 表示 gcd g c d 刚好为 k∗i k ∗ i 的选数方案，那么 f[1] f [ 1 ] 就是答案，我们就for i = 100000 to 1，从大往小算

对于每一个 i i ，先算在这个区间里面有多少个k∗ik∗i的倍数，然后 N N 次方之

然后减去f[i∗j](j=1,2,3….MAXJ)f[i∗j](j=1,2,3….MAXJ)

这就是 gcd g c d 为 k∗i k ∗ i 的方案数

i∗j i ∗ j 到 100000 100000 就好了，因为这个区间最多只有 100000 100000 长

可能 i∗j i ∗ j 在 100000 100000 以上还会有需要减掉的，我们考虑计算这些数对答案的贡献

首先同一个 gcd g c d 只会有1个数，这些 gcd g c d 的个数就是在原区间里面除以 K>100000 K > 100000 且为 i i <script type="math/tex" id="MathJax-Element-64">i</script>的倍数的数