Counting Arrays

发表于 2023-07-13 分类于 codeforces ， practice

对于数组$a_1, a_2, \cdots, a_n$，我们每次可以移除一个值$a_i$，必须满足$gcd(a_i,i) = 1$，然后将后续的数字前移动。

在移除前一个空数组b。每次移除值$a_i$后将下标$i$加入到b中。

如果存在多种移除序列b将数组a全部移除，那么a就是不明确数组。

现在问一个长度为1到n的数组，每个元素的范围在1到m。能形成多少种不明确数组。

Created by LXC on Tue Jul 11 09:24:14 2023

ranting: 1900

tag: combinatorics, dp, math, number theory

problem

对于数组$a_1, a_2, \cdots, a_n$，我们每次可以移除一个值$a_i$，必须满足$gcd(a_i,i) = 1$，然后将后续的数字前移动。

在移除前一个空数组b。每次移除值$a_i$后将下标$i$加入到b中。

如果存在多种移除序列b将数组a全部移除，那么a就是不明确数组。

现在问一个长度为1到n的数组，每个元素的范围在1到m。能形成多少种不明确数组。

如果能够将数组a完全移除，那么一定存在全为1的数组b。

所以我们只能每次移除$a_1$，才能保证数组是明确数组。

那么我们可以求出所有数组的组合情况，然后减去明确数组的数量，以得到不明确数组的数量。

所有数组的组合情况显然是$\sum \limits_{i=1}^{n} m^i$

对于求明确数组，我们需要保证原始数组a中$a_i$与2到i的每个数的最大公约数不等于1，其实就是说$a_i$需要包含2到i内所有的质数因子。用m除以当前这些质因子的乘积向下取整即可得到当前$a_i$的个数。

可以预先用线性筛求出所有质数。