HDUOJ 5514 - Frogs

题面

现有 mm 块石头围成一个圈(标记为 0m10 \sim m - 1),nn 只蛤在上面跳。

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

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

数据范围

1n1041 \le n \le 10^4

1m,ai1091 \le m, a_i \le 10^9

题目链接

分析

首先我们考虑只有一只蛤的情景(记它的步长为 aa)。这实际上就是求 kamodmk \cdot a \bmod m 有哪些值的一个数论问题。换句话说,就是解这样一个方程:
x=katmx = 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 的蛤就会占据所有标号为 lkl \cdot k,其中 kk 可取 [1,ml][1, \frac{m}{l}] 中所有与 ml\frac{m}{l} 互质的数。


我们可以用反证的思想考虑一下。假设所取 kkml\frac{m}{l} 不互质,不妨记 k=gt1, ml=gt2k = g \cdot t_1, \ \frac{m}{l} = g \cdot t_2,即:m=glt2m = gl \cdot t_2。这样一来,当前石头的标号就可以表示为:
i=lk=glt1i = l \cdot k = gl \cdot t_1

故:
gcd(i,m)=gll\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) = 1ii 之和,由:
gcd(x,i)=gcd(x,xi)\gcd(x, i) = \gcd(x, x - i)
假设 i=xii = 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 互素的数 iixix - i 必然是成对出现的,不会出现 i=xii = x - i 的情况。

我们知道 gcd(x,i)=1\gcd(x, i) = 1ii 的个数即 φ(x)\varphi(x)。我们可以将这些数按照上面证明的方式划分为 12φ(x)\frac{1}{2} \varphi(x) 个数对 x,xi\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,而新引入的虚拟蛤步长为 klk \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 (242 | 4) 和 66 (363|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{104} 了解一下(逃……

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

我们不难注意到在计算步长为 ll 的蛤时,我们重复地算了本该在计算 2l,3l,mll2l, 3l, \dots \frac{m}{l} \cdot l 等步长蛤时加入的值。我们不妨考虑给步长为 ll 的蛤的答案乘上一个系数贡献值,初始时显然为 11。那么在这种情况下,我们只需要对 2l,3l,mll2l, 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,其中 4466 都是现有步长之一的倍数,所以加进来是并不影响答案的,同时我们容斥的时候用得上。对于 2, 3, 4, 62, \ 3, \ 4,\ 6 答案的贡献值我们都初始化为 11

  • 步长为 22 的答案贡献值为 11,由于计算 22 时等于重复计算了本该在 4, 64, \ 6 处计算的值,所以 4, 64, \ 6 的贡献值要减去 22 的贡献值,也就是 11。由此一来,4466 的贡献值都变成 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} 级别的,所以放心搞吧(逃

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/10/03/hduoj-5514/