DDOSvoid's Blog

CF 900D Unusual Sequences

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

http://codeforces.com/problemset/problem/900/D

简要题意：给定 $x$​ 和 $y$​，求有多少序列，满足 $gcd$​ 是 $x$​，和是 $y$，序列中的数必须是正整数

$1\le x,y \le 10^9$

Solution

我们首先令 $m=\frac{y}{x}$​，注意到如果 $y$ 不整除 $x$，那么一定无解

首先我们不考虑 $gcd$ 的问题，我们只考虑和为 $n$ 的序列的数量，容易得到 $\sum_{i=1}^n\binom{n-1}{i-1}=2^{n-1}$

然后我们考虑容斥，令 $f(n)$​ 表示和为 $m$​，$gcd$​ 是 $n$​ 的倍数的序列的数量，$g(n)$​ 表示和为 $m$​，$gcd$​ 是 $n$​ 的序列的数量那么答案就是 $g(1)$​

容易写出 $f(n)$ 的式子，$f(n)=\sum_{n|d}g(d)=2^{\frac{m}{n}-1}$​

根据莫比乌斯反演，$g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)$

注意到数列的 $gcd$ 一定是和的约数，所以 $g(1)=\sum_{d|m}\mu(\frac{d}{m})f(d)$​

时间复杂度大概是 $O(\sigma_0(n)\sqrt n)$，不过实际上跑得飞快

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
51
52
53
54
55
#include <iostream>
#include <cmath>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

int pri[maxn], cnt; bool isp[maxn];
void init_isp(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }
}

int mu(int x) {
    ll ans = 1;
    for (int i = 1; i <= cnt && pri[i] <= x / pri[i]; ++i) 
        if (x % pri[i] == 0) {
            int s = 0; 
            while (x % pri[i] == 0) ++s, x /= pri[i];
            if (s > 1) return 0; ans *= -1;
        }
    if (x > 1) ans *= -1; return ans;
}

int x, y, n;

ll solve(int d) { return mu(d) * pow_mod(2, n / d - 1) % p; } 

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> x >> y; n = y / x; init_isp(sqrt(n));
    if (y % x) return cout << 0 << "\n", 0;
    ll ans = 0; 
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) ans = (ans + solve(i)) % p;
        if (n % i == 0 && i * i != n) ans = (ans + solve(n / i)) % p; 
    } cout << (ans + p) % p << "\n";
    return 0;
}