「Codeforces 900D」Unusual Sequences

发表于 | | 阅读次数:
字数统计: 901 字

Description

题目链接：Codeforces 900D

求满足下面两个条件的数列 $a_1,a_2,\dots,a_n(1\le a_i)​$ 的个数（答案对 $10^9+7​$ 取模）：

  1. $\gcd(a_1,a_2,\dots,a_n)=x$
  2. $\sum_{i=1}^n a_i=y​$

数据范围：$1\le x.y\le 10^9​$

Solution

如果在 $x\nmid y​$ 的情况下，显然无解。

我们令 $m=\frac{y}{x}​$，那么问题转化为：求满足 $\gcd(a_1,a_2,\dots,a_n)=1​$ 且 $\sum_{i=1}^n a_i=m​$ 的数列个数。

我们先不考虑 $\gcd=1$ 的限制，设 $g(x)$ 表示 $\sum_{i=1}^n a_i=x$ 的数列个数。

对于 $g(x)​$ 的值，我们可以使用隔板法求解：

我们发现，$g(x)$ 的值又可以通过 $f(x)​$ 求得：

接下来介绍两种做法：

递推

我们可以考虑容斥原理：所有序列数量减去不合法的序列数量。我们枚举不合法的序列的 $\gcd$ 记为 $d$，显然 $d$ 必须满足 $d\mid x,d>1$，这样的序列数量为 $f\left(\frac{x}{d}\right)$（当然也可以通过 $g$ 和 $f$ 的关系得到）。

由于一个数的因子的因子也一定是这个数的因子，所以我们发现需要的 $x​$ 为 $d(m)​$ 个，即不超过 $O(\sqrt m)​$ 个，可以直接递归求解。

时间复杂度：$O(d(m)\sqrt m\log m)​$

反演

我们发现：

这个式子的本质是 $g=f\ast 1$，通过莫比乌斯反演可以得到：

这样一来我们就可以直接暴力求解了。

时间复杂度：$O\left(\frac{m}{\log m}\right)​$

Code

递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include <cstdio>
#include <map>

const int mod=1e9+7;
std::map<int,int> mp;

int pow(int x,int p) {
    int ret=1;
    for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ret=1LL*ret*x%mod;
    return ret;
}
void upd(int &x,int y) {
    (x+=y)>=mod&&(x-=mod);
}
int solve(int n) {
    if(n==1) return 1;
    if(mp.count(n)) return mp[n];
    int ans=0;
    for(int i=2;i*i<=n;++i) {
        if(n%i==0) {
            upd(ans,solve(i));
            if(i*i!=n) upd(ans,solve(n/i));
        }
    }
    upd(ans,solve(1));
    ans=(pow(2,n-1)-ans+mod)%mod;
    return mp[n]=ans;
}
int main() {
    int x,y;
    scanf("%d%d",&x,&y);
    if(y%x) return puts("0"),0;
    printf("%d\n",solve(y/x));
    return 0;
}

反演

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include <cstdio>

const int N=1e5+5;
const int mod=1e9+7;
int x,y,tot,p[N];
bool flg[N];

void sieve(int n) {
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
int mu(int n) {
    int cnt=0;
    for(int i=1;i<=tot&&1LL*p[i]*p[i]<=n;++i) {
        if(n%p[i]) continue;
        int now=0;
        while(n%p[i]==0) n/=p[i],++now;
        if(now>1) return 0;
        ++cnt;
    }
    if(n>1) ++cnt;
    return cnt%2==0?1:mod-1;
}
int pow(int x,int p) {
    int ret=1;
    for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ret=1LL*ret*x%mod;
    return ret;
}
void upd(int &x,int y) {
    (x+=y)>=mod&&(x-=mod);
}
int main() {
    sieve(N-5);
    scanf("%d%d",&x,&y);
    if(y%x) return puts("0"),0;
    int n=y/x,ans=0;
    for(int i=1;1LL*i*i<=n;++i) {
        if(n%i==0) {
            upd(ans,1LL*mu(n/i)*pow(2,i-1)%mod);
            if(i*i!=n) upd(ans,1LL*mu(i)*pow(2,n/i-1)%mod);
        }
    }
    printf("%d\n",ans);
    return 0;
}
0%