Project Euler 281

发表于 更新于 分类于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 2 分钟

Project Euler 281

题目

Pizza Toppings

You are given a pizza (perfect circle) that has been cut into \(m\cdot n\) equal pieces and you want to have exactly one topping on each slice. Let \(f(m,n)\) denote the number of ways you can have toppings on the pizza with \(m\) different toppings \((m\ge2)\), using each topping on exactly \(n\) slices \((n\ge1)\).

Reflections are considered distinct, rotations are not.

Thus, for instance, \(f(2,1)=1, f(2,2)=f(3,1)=2\) and \(f(3,2)=16\). \(f(3,2)\) is shown below:

Find the sum of all \(f(m,n)\) such that \(f(m,n)\le10^{15}\).

解决方案

Burnside 引理

设群 \(G=C_L\)，即所有旋转 \(k\)（把位置 \(i\) 送到 \(i+k\pmod L\)），群大小 \(|G|=L\)。

Burnside 引理给出不同旋转等价类（即 \(f(m,n)\)）为

\[ f(m,n)=\frac{1}{|G|}\sum_{k=0}^{L-1}\mathrm{Fix}(k), \]

其中 \(\mathrm{Fix}(k)\) 是在旋转 \(k\) 下保持不变（被该旋转固定）的合法着色数。

回到问题，把披萨的 \(m\cdot n\) 片按顺时针编号为 \(0,1,\dots,L-1\)，其中 \(L=mn\)。给每片赋一个“配料颜色”，共有 \(m\) 种颜色，每种颜色恰好出现 \(n\) 次。

因此我们在数的是长度为 \(L\) 的序列 \((a_0,a_1,\dots,a_{L-1})\)，其中颜色集合大小为 \(m\)，且每种颜色出现次数为 \(n\)，并且把循环移位（旋转）视作同一个。

令 \(d=\gcd(L,k)\)。旋转 \(k\) 会把 \(L\) 个位置分解成 \(d\) 个循环，每个循环长度为\(c=\dfrac{L}{d}.\)

若一个着色在旋转 \(k\) 下不变，则同一循环里的位置必须颜色相同，否则旋转后会改变序列。因此：

  • 每个循环贡献 \(c\) 个相同颜色的格子；
  • 总共有 \(d\) 个循环要分配颜色。

因为每个循环贡献的数量是 \(c\)，所以某种颜色出现次数必为“该颜色被分到的循环数 \(\times c\)”。要等于 \(n\)，必须满足\(c\mid n.\)

把 \(c=L/d=mn/d\) 代入，条件变为\(\dfrac{mn}{d}\mid n \Longleftrightarrow mn \mid nd \Longleftrightarrow m\mid d.\)

而 \(d=\gcd(mn,k)\)，要让 \(m\mid d\)，等价于 \(m\mid k\)（因为 \(m\mid mn\)，只有当 \(k\) 含有 \(m\) 的全部质因子时 \(\gcd\) 才能含 \(m\)）。

因此：

  • 若 \(m\nmid k\)，则 \(\mathrm{Fix}(k)=0\)；
  • 只需考虑 \(k=mt\)，其中 \(t=0,1,\dots,n-1\)（因为 \(0\le k<L=mn\)）。

设 \(k=mt\)，则\(d=\gcd(mn,mt)=m\gcd(n,t)=mg,\)其中令\(g=\gcd(n,t)\)。

于是循环长度\(c=\dfrac{L}{d}=\dfrac{mn}{mg}=\dfrac{n}{g}\)，循环个数是 \(d=mg\)。

每个循环必须同色。设某颜色被分到 \(r\) 个循环，则它贡献的片数为\(r\cdot c=r\cdot\dfrac{n}{g}\)。

要等于 \(n\)，必须有\(r\cdot\dfrac{n}{g}=n\Longleftrightarrow r=g.\)

也就是说：每种颜色必须恰好占 \(g\) 个循环。总循环数为 \(mg\)，把它们分给 \(m\) 个颜色、每色 \(g\) 个循环，方案数是多项式系数：

\[ \mathrm{Fix}(k)=\frac{(mg)!}{(g!)^m}. \]

现在只对 \(k=mt\) 求和。对 \(t\in{0,1,\dots,n-1}\)，令 \(g=\gcd(n,t)\)。

固定一个 \(g\mid n\)，满足 \(\gcd(n,t)=g\) 的 \(t\) 个数为\(\varphi\left(\dfrac{n}{g}\right)\)，其中 \(\varphi\) 为欧拉函数。

因此

\[ \sum_{k=0}^{L-1}\mathrm{Fix}(k)=\sum_{t=0}^{n-1}\mathrm{Fix}(mt)=\sum_{g\mid n}\varphi\left(\frac{n}{g}\right)\cdot \frac{(mg)!}{(g!)^m}. \]

最终得到：

\[ f(m,n)=\frac{1}{mn}\sum_{g\mid n}\varphi\left(\frac{n}{g}\right)\frac{(mg)!}{(g!)^m}. \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from tools import *
from itertools import count

M = 10 ** 15
def f(m,n):
    s = 0
    for g in divisors(n):
        s += phi(n // g) * fac(m * g) // pow(fac(g), m)
    return s // m // n

ans = 0
for n in count(1):
    w = f(2, n)
    if w > M:
        break
    ans += w
    for m in count(3):
        w = f(m,n)
        if w > M:
            break
        ans += w
print(ans)