题面

现有 mm 块石头围成一个圈（标记为 0∼m−10 \sim m - 1 ），nn 只蛤在上面跳。

第 ii 只蛤从 00 号石头开始跳，每一次跳跃恰好跳过 aia_i 块石头。也就是说，如果蛤当前在第 jj 块石头上，那么它下一次将跳到第 (j+ai) mod m(j + a_i) \bmod m 块石头上。

每当一只蛤跳到一块石头上，它就会对这块石头 “宣布主权”，一块石头可以被多只蛤 ”宣布主权”。求这 mm 块石头中至少会被一只蛤 “宣布主权” 的所有石头的标号之和。

数据范围：

1≤n≤1041 \le n \le 10^4

1≤m,ai≤1091 \le m, a_i \le 10^9

题目链接

分析

首先我们考虑只有一只蛤的情景（记它的步长为 aa ）。这实际上就是求 k⋅a mod mk \cdot a \bmod m 有哪些值的一个数论问题。换句话说，就是解这样一个方程：

x=ka−tm x = ka - tm

根据拓展欧几里得定理，xx 的最小整数解即 gcd⁡(a,m)\gcd(a, m) ，则该方程的整数解一定是 gcd⁡(a,m)\gcd(a, m) 的倍数。换句话说，可以把蛤的步长等效地看作 gcd⁡(a,m)\gcd(a, m) 。由此，出现的所有值的和为：

gcd⁡(a,m)⋅[0+1+2+⋯+mgcd⁡(a,m)] \gcd(a, m) \cdot \left [ 0 + 1 + 2 + \dots + \frac{m}{\gcd(a, m)} \right ]

那么回到有多只蛤的情景，我们需要解决的最大问题就是如何去重（一块石头可以被多只蛤 “宣布主权”）。有两种巧妙的方法可以解决这一问题：数论与容斥。

数论做法

分析

对于被多只蛤 “宣布主权” 的石头，我们不妨考虑对其进行某种规定使得它一定只属于一只蛤（尽管这只蛤可能不存在）：

规定编号为 ii 的石头只被步长为 gcd⁡(i,m)\gcd(i, m) 的蛤占领。

这样一来，步长为 ll 的蛤就会占据所有标号为 l⋅kl \cdot k ，其中 kk 可取 [1,ml][1, \frac{m}{l}] 中所有与 ml\frac{m}{l} 互质的数。

我们可以用反证的思想考虑一下。假设所取 kk 与 ml\frac{m}{l} 不互质，不妨记 k=g⋅t1, ml=g⋅t2k = g \cdot t_1, \ \frac{m}{l} = g \cdot t_2 ，即：m=gl⋅t2m = gl \cdot t_2 。这样一来，当前石头的标号就可以表示为：

i=l⋅k=gl⋅t1 i = l \cdot k = gl \cdot t_1

故：

gcd⁡(i,m)=gl≠l \gcd(i, m) = gl \neq l

与规定矛盾，得证一定是互质的。

既然互质，我们求和的时候可以借助一个结论：

在 [1,x][1, x] 中与 xx 互素的数的和为：

12φ(x)⋅x \frac{1}{2} \varphi(x) \cdot x

下面附上一个简单推导：

我们所要求的就是对于所有满足 gcd⁡(x,i)=1\gcd(x, i) = 1 的 ii 之和，由：

gcd⁡(x,i)=gcd⁡(x,x−i) \gcd(x, i) = \gcd(x, x - i)

假设 i=x−ii = x - i ，那么有 x=2ix = 2i ，并且 gcd⁡(x,i)=i\gcd(x, i) = i 。我们先考虑 x>2x > 2 的情况，这样显然就与条件 gcd⁡(x,i)=1\gcd(x, i) = 1 矛盾了。因此对于 x>2x > 2 ，与 xx 互素的数 ii 与 x−ix - i 必然是成对出现的，不会出现 i=x−ii = x - i 的情况。

我们知道 gcd⁡(x,i)=1\gcd(x, i) = 1 的 ii 的个数即 φ(x)\varphi(x) 。我们可以将这些数按照上面证明的方式划分为 12φ(x)\frac{1}{2} \varphi(x) 个数对 ⟨x,x−i⟩\langle x, x - i\rangle ，每个数对的和为 xx ，所以当 x>2x > 2 时 [1,x][1, x] 中与 xx 互素的数的和为：

12φ(x)⋅x \frac{1}{2} \varphi(x) \cdot x

通过代入 x=2x = 2 ，我们不难发现这对 x=2x = 2 也成立。

我们剩下解决的问题是，可能石头 ii 可被跳到但是我们规定其属于的那只蛤不存在。在这种情况下我们当然是要假装它存在了。在引入虚拟蛤时，如果存在某蛤步长为 ll ，而新引入的虚拟蛤步长为 k⋅lk \cdot l ，那么这显然都答案是没有任何影响的。根据规定，能占有石头的蛤的步长 ll 一定是 mm 的约数，所以我们可以考虑预处理出 ll 的所有约数。 对于蛤 jj ，若 aja_j 可整除 mm 的某因数 ss ，则考虑加入 ss 作为虚拟蛤，同时应用上面的公式计算出这只蛤所占有的石头下标之和。

也就是说，我们借助引入不影响答案的虚拟蛤，将石头分配给虚拟蛤就可以进行计算了。巧妙而完美。

例子

我们以第一组样例举一个例子：

2 12
9 10

对于第一只蛤，其等效步长为 gcd⁡(9,12)=3\gcd(9, 12) = 3 ，因此它可以跳到的石头有：0, 3, 6, 90, \ 3, \ 6, \ 9 。

对于第二只蛤，其等效步长为 gcd⁡(10,12)=2\gcd(10, 12) = 2 ，因此它可以跳到的石头有：0, 2, 4, 6, 8, 100, \ 2, \ 4, \ 6, \ 8, \ 10 。

我们预处理出 1212 所有小于自身的约数：1, 2, 3, 4, 61, \ 2, \ 3, \ 4, \ 6 。除去本身就存在的 2, 32, \ 3 ，我们需要引入 44 (2∣42 | 4 ) 和 66 (3∣63|6 ) 作为虚拟蛤。根据我们上面的规定：

  • 2, 102, \ 10 被步长为 22 的蛤占据，和为 2×(1+5)2 \times (1 + 5) ；
  • 3, 93, \ 9 被步长为 33 的蛤占据，和为 3×(1+3)3 \times (1 + 3) ；
  • 4, 84, \ 8 被步长为 44 的蛤占据，和为 4×(1+2)4 \times (1 + 2) ；
  • 66 被步长为 66 的蛤占据，和为 6×16 \times 1 。

不难发现，只有引入虚拟蛤我们才能不遗漏地将石头分配下去，并巧妙地避免重复从而计算出答案。

实现

欧拉函数貌似预处理的话存不下…… 那就 O(N)\mathcal{O}(\sqrt{N}) 暴力算吧。

完整参考代码

容斥做法

分析

虽然容斥是很容易想到的方向，但是暴力容斥显然是不可行的，21042^{10^4} 了解一下（逃……

那怎么办？可以考虑往贡献值的方向去思考……

我们不难注意到在计算步长为 ll 的蛤时，我们重复地算了本该在计算 2l,3l,…ml⋅l2l, 3l, \dots \frac{m}{l} \cdot l 等步长蛤时加入的值。我们不妨考虑给步长为 ll 的蛤的答案乘上一个系数贡献值，初始时显然为 11 。那么在这种情况下，我们只需要对 2l,3l,…ml⋅l2l, 3l, \dots \frac{m}{l} \cdot l 步长蛤的答案的贡献值减去步长为 ll 的蛤的答案的贡献值即可达到去重的效果（如果不好理解建议参照例子）。

例子

我们依然以第一组样例举一个例子：

2 12
9 10

对于第一只蛤，其等效步长为 gcd⁡(9,12)=3\gcd(9, 12) = 3 ，因此它可以跳到的石头有：0, 3, 6, 90, \ 3, \ 6, \ 9 。

对于第二只蛤，其等效步长为 gcd⁡(10,12)=2\gcd(10, 12) = 2 ，因此它可以跳到的石头有：0, 2, 4, 6, 8, 100, \ 2, \ 4, \ 6, \ 8, \ 10 。

我们预处理出 1212 所有小于自身的约数：1, 2, 3, 4, 61, \ 2, \ 3, \ 4, \ 6 。除去现有的 2, 32, \ 3 ，其中 44 和 66 都是现有步长之一的倍数，所以加进来是并不影响答案的，同时我们容斥的时候用得上。对于 2, 3, 4, 62, \ 3, \ 4,\ 6 答案的贡献值我们都初始化为 11 。

  • 步长为 22 的答案贡献值为 11 ，由于计算 22 时等于重复计算了本该在 4, 64, \ 6 处计算的值，所以 4, 64, \ 6 的贡献值要减去 22 的贡献值，也就是 11 。由此一来，44 和 66 的贡献值都变成 00 了。答案增加了 1×(2+4+6+8+10)1 \times (2 + 4 + 6 + 8 + 10) ；
  • 步长为 33 的答案贡献值为 11 ，同理 66 的贡献值要减去 11 。答案增加了 1×(3+6+9)1 \times (3 + 6 + 9) ；
  • 步长为 44 的答案贡献值为 00 。答案增加了 00 ；
  • 步长为 66 的答案贡献值为 −1-1 ，答案减少了 1×61 \times 6 。

可以看到我们用贡献值的思想完美地容斥掉了多算的 66 。

实现

对于 10910^9 级别的数因数个数大致是 109\sqrt{10^9} 级别的，所以放心搞吧（逃

完整参考代码

%%%