原题呈现

排列数#

题目描述#

排列数的符号为 $A_j^i$ ，意为从 $j$ 个物品中任选 $i$ 个，并按照任意顺序排成一列的方案数．和组合数不同，排列数与选出物品的顺序有关．

以琪露诺的智商当然学不明白排列数的含义，所以她把公式背了下来：

A_j^i = \frac{j!}{(j-i)!}

幸运的是，期末考试的压轴大题刚好考了排列数．题目是这样的：求有多少对 $(i, j)$ ，满足 $1 \le i \le j \le n$ 且 $A_j^i$ 为 $k$ 的倍数．

可惜只背公式当然是没什么用的，琪露诺完全不会这个题目，你能帮帮她吗？

输入格式#

输入仅一行，包含两个整数 $n, k$ ，表示排列数的大小限制与倍数限制．

输出格式#

输出仅一个整数，表示满足 $1 \le i \le j \le n$ 且 $A_j^i$ 为 $k$ 的倍数的有序数对 $\{i, j\}$ 的数量．

样例#

输入 #1#

1
10 1

输出 #1#

1
55

输入 #2#

1
10 6

输出 #2#

1
43

输入 #3#

1
100 66

输出 #3#

1
4540

样例解释#

样例一中，满足 $1 \le i \le j \le 10$ 的任意 $A_j^i$ 都是 $1$ 的倍数，共 $\binom{10+1}{2}=55$ 个．
样例二中，符合范围条件但是不是 $6$ 的倍数的排列数有：

A_1^1,\ A_2^1,\ A_2^2,\ A_3^1,\ A_4^1,\ A_5^1,\ A_5^2,\ A_7^1,\ A_8^1,\ A_8^2,\ A_9^1,\ A_{10}^1

共 $12$ 个．因此符合条件的为 $55 - 12 = 43$ 个．

数据范围#

数据包	分数	$n \le$	$k \le$	特殊性质
1	30	$10^{100}$	$10$	无
2	10	$300$	$10^6$	无
3	10	$3000$	$10^6$	无
4	10	$10^6$	$2$	无
5	10	$10^6$	$100$	无
6	10	$10^6$	$10^9$	A
7	20	$10^6$	$10^9$	无

特殊性质 A：保证 $k$ 为质数．

对于所有数据：

$1 \le n \le 10^6$
$1 \le k \le 10^9$

我们可以将排列数的公式变一下形，为：

A^i_j=(j-i+1)(j-i+2)\cdots j

那么只需要求所有乘积是 $k$ 的倍数的区间数量．显然，若一个区间乘积已经是 $k$ 的倍数了，后面不管加多少数，都是 $k$ 的倍数．因此，对于所有增加一个数之后恰好可以满足条件的区间，其贡献是这个区间后面数的数量 +1，因为可以增加任意数量（可以为 0）的后面的数．（为什么不加前面的数？加上前面的数的区间会在前面被计算过一次，再增加一次会导致重复）、

具体的，使用双指针来维护．一个指针 $i$ 指向当前区间的起点，一个指针 $j$ 指向当前区间的终点．若当前区间积还不是 $k$ 的倍数，那么尝试增加一个数满足限制，让指针 $j$ 前进，直到满足要求．此时这个区间的贡献是区间后面还有多少不在区间内的数，再 +1．那么这样以 $i$ 开头的区间全部统计完成了，让 $i$ 前进一步．

还有一些问题：如何判断一个区间的区间积是 $k$ 的倍数？

如果强行计算进行比较的话 __int128 都存不下，实际上，记录区间中所有数字乘积的分解质因数的结果，再和 $k$ 分解之后的结果进行比较即可．

那问题又来了， $k$ 的值域限制是 $k \leq 10^9$ ，这无法对 $k$ 进行质因数分解，怎么办呢？实际上，有一个小观察：若 $k$ 拥有一个质因数 $p$ 满足 $p>n$ ，则答案为 0．这也很好理解，如果 $k$ 拥有这样的 $p$ ，则无论如何，乘积都不可能有大于每个数本身的质因数．对 $k$ 花费 $\sqrt{k}$ 的时间复杂度预处理一下即可．

分解质因数

实践中常常需要我们对于一个数进行分解质因数操作，这该如何实现呢？

分解质因数，首先需要知道质数．这里重点介绍线性筛质数这一种方法．

对于一个未确定的数，我们进行以下流程：

若这个数未被标记过，则这个数是质数．
接下来，无论这个数是否被标记过，都用它乘上所有已知的质数 $p$ ，设所得结果为 $x$ ，则将 $x$ 标记．可以证明， $p$ 是 $x$ 的最小质因数．

以下程序在记录质数的同时，记录了每一个数的最小质因数（ $spf$ ）．

1
void calPrime() {
2
    for (int i = 2; i <= N; i++) {
3
        if (spf[i] == 0) {
4
            primes.push_back(i);
5
        }
6
        for (int j = 0; j < primes.size(); j++) {
7
            int pr = primes[j];
8
            if (pr * i > N)
9
                break;
10
            spf[pr * i] = pr;
11
        }
12
    }
13
}

知道了每一个数的最小质因数之后，就可以快速对一个数分解质因数．

具体来说，当想要分解一个数 $x$ 时，将其除以其最小质因数 $p$ ，这样在将 $p$ 作为贡献之后，原问题就转化为了规模更小的子问题：分解 $\frac{x}{p}$ ，直到 $spf_x=0$ 时，就是该问题的边界，此时 $x$ 也是质数（或 0），加入贡献．

以下程序在上面程序的基础上，计算了 $x$ 的质因数：

1
typedef pair<int, int> pii;
2
vector<pii> ans;
3
while (true) {
4
  if (spf[x] == 0) {
5
    if (x != 1)
6
      ans.push_back({x, 1});
7
    break;
8
  }
9
  int pr = spf[x];
10
  pii rd = {pr, 0};
11
  while (true) {
12
    if (x % pr)
13
      break;
14
    rd.second++;
15
    x /= pr;
16
  }
17
  ans.push_back(rd);
18
}
19
return ans;

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef pair<int, int> pii;
5
const int N = 1e6 + 100;
6
int n, k;
7
ll ans;
8
vector<int> primes;
9
vector<pii> stdpr;
10
int spf[N];
11
unordered_map<int, int> um;
12

13
void calPrime() {
14
    for (int i = 2; i <= N - 10; i++) {
15
        if (spf[i] == 0) {
16
            primes.push_back(i);
17
        }
18
        for (int j = 0; j < primes.size(); j++) {
19
            int pr = primes[j];
20
            if (pr * i > N - 10)
21
                break;
22
            spf[pr * i] = pr;
23
        }
24
    }
25
}
26

27
vector<pii> calpr(int x) {
28
    vector<pii> ans;
29
    while (true) {
30
        if (spf[x] == 0) {
31
            if (x != 1)
32
                ans.push_back({x, 1});
33
            break;
34
        }
35
        int pr = spf[x];
36
        pii rd = {pr, 0};
37
        while (true) {
38
            if (x % pr)
39
                break;
40
            rd.second++;
41
            x /= pr;
42
        }
43
        ans.push_back(rd);
44
    }
45
    return ans;
46
}
47

48
bool isAllow() {
49
    for (int i = 0; i < stdpr.size(); i++) {
50
        int pr = stdpr[i].first;
51
        if (um[pr] < stdpr[i].second) {
52
            return false;
53
        }
54
    }
55
    return true;
56
}
57

58
void insert(int x) {
59
    vector<pii> vec = calpr(x);
60
    for (int i = 0; i < vec.size(); i++) {
61
        int pr = vec[i].first;
62
        um[pr] += vec[i].second;
63
    }
64
}
65

66
void remove(int x) {
67
    vector<pii> vec = calpr(x);
68
    for (int i = 0; i < vec.size(); i++) {
69
        int pr = vec[i].first;
70
        um[pr] -= vec[i].second;
71
    }
72
}
73

74
signed main() {
75
    ios::sync_with_stdio(false);
76
    cin.tie(0);
77
    cout.tie(0);
78
    freopen("num.in", "r", stdin);
79
    freopen("num.out", "w", stdout);
80
    cin >> n >> k;
81
    calPrime();
82
    if (k == 1) {
83
        cout << 1ll * (1 + n) * n / 2;
84
        return 0;
85
    }
86
    for (int i = 0; i < primes.size(); i++) {
87
        if (k % primes[i] == 0) {
88
            pii t = {primes[i], 0};
89
            while (k % primes[i] == 0) {
90
                k /= primes[i];
91
                t.second++;
92
            }
93
            if (t.second != 0)
94
                stdpr.push_back(t);
95
        }
96
    }
97
    if (k != 1) {
98
        cout << 0;
99
        return 0;
100
    }
101
    int i = 1, j = 1;
102
    while (i <= n) {
103
        if (isAllow()) {
104
            ans += 0ll + n - i + 1;
105
            remove(j);
106
            j++;
107
            if (i < j) {
108
                i++;
109
                insert(i);
110
            }
111
        } else {
112
            i++;
113
            insert(i);
114
        }
115
    }
116
    cout << ans;
117
}

音乐

音乐

排列数#

题目描述#

输入格式#

输出格式#

样例#

输入 #1#

输出 #1#

输入 #2#

输出 #2#

输入 #3#

输出 #3#

样例解释#

数据范围#

文章分享

音乐

安吉D19 T1

排列数#

题目描述#

输入格式#

输出格式#

样例#

输入 #1#

输出 #1#

输入 #2#

输出 #2#

输入 #3#

输出 #3#

样例解释#

数据范围#

文章分享