【2024/7/7】部分情况割圆多项式的展开式求解方式研究

我是Pi***

0x00 前置

割圆多项式又称分圆多项式。

一般地，我们定义 n 次割圆多项式为由所有 n 次本原单位根构成的多项式。

我们用 Φ_n(x) 来表示。

研究割圆多项式的意义在于（好像没有意义），它在数论中引进了欧拉函数、欧拉定理等，如在研究莫比乌斯反演、快速傅里叶变换等等技巧时，可以研究其作为铺路砖。

最常见的应用是求解形如 x^n-1 的方程的根。

读不懂以上内容没有关系，只要观察我以下几道简单又有规律的例题，你就能知道割圆多项式这个知识....的三分之一。

碍于论坛没有 Latex / Katex 显示，故只能手打公式。

本文需在我的同意下转载，仅供学术研究，谢谢。

另附一首小诗。

西江月·证明 佚名

即得易见平凡，仿照上例显然。留作习题答案略，读者自证不难。
反之亦然同理，推论自然成立，略去过程QED，由上可知证毕。

0x01 结果展示

省流：

本文浅显研究了关于 (x^n)-1 在割圆多项式上的运用、p^k （其中 p 为任意质数，k 为一正整数）次割圆多项式之展开式展开这两项技巧。

例 1 （2024 · iridOI · 1）我们知道，x^n-1 可以展开为 k 个割圆多项式的积。为方便表示，我们用 a_i 表示该展开式中第 i 个割圆多项式的次数。题目从标准输入输入一个正整数 n，请你输出所有符合条件的 a_i。特别地，你需要将该结果按照割圆多项式的次数升序排序。例如，题目输入 998244353，你需要从标准输出输出 1 998244353。

我们在求 x^n-1 的根时可以引入割圆多项式解决问题。

定理 不同次的 本原单位根 之间无交集，且全体满足 d | n 的 d 次 本原单位根 构成的集合，恰为全体 n 次 单位根 之集合。

证明略。此为基本定理。

应用在该题上，根据割圆多项式定义，x^n-1 就等于所有 n 的因数 次割圆多项式的积。

这道题巧妙地化用了该概念和分解因数，那么只要我们输出 n 的所有因数就可以通过。

#include<bits/stdc++.h>
using namespace std;
int main(){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
                if(n%i==0){
                        cout<<i<<" ";
                }
        }
        return 0;
}

例 2 （2024 · iridOI · Ex）给定素数 p，请你输出 p 次割圆多项式的展开式。

定理 Φ_p(x)=x^(p-1)+x^(p-2)+x^(p-3)+...+x+1.

证明 由于 p 是素数，因此除了 1 以外的所有 p 次单位根都是本原单位根。因此 Φ_p(x) = ((x^p)-1) / (x-1) = x^(p-1)+x^(p-2)+x^(p-3)+...+x+1.

那么，在求解 p 次割圆多项式的展开式时，只要给定次数 p，我们就可以依据暴力法暴力求解。

思路很好理解，特判 x^1 和 x^0 情况即可。

namespace st1{
        void calc(int n){
                if(n==1){
                        printf("x-1");
                        return;
                }
                for(int ni=n-1;ni>=2;ni--){
                printf("x^%d+",ni);
            }
            printf("x+1");
            return;
        }
}

这些知识只是我们研究下一个问题的垫脚石。

例 3（2024 · iridOI · Ex）给定素数 p 和整数 k (1≤k)，请你输出 p^k 次割圆多项式的展开式。

定理 对于素数 p ，Φ_p^k(x) = Φ_p(x^(p^(k-1)))，其中 p 为一质数，k 为一正整数。

如何求解它的展开式呢？这时我们需要发挥观察力。不妨列出几个 p^k 次割圆多项式的展开式。

我们对于前 30 个小于 105（因为 105 次割圆多项式的系数不属于 {-1,0,1}）的割圆多项式进行展开，可得到：

• 图源 Wikipedia，侵删，上传自作者本人的洛谷图床。

在图上我们可以发现，对于所有的 Φ_p^k(x) ，我们提取 x 和 p^k 次割圆多项式展开式中 x 的所有次数（规定 x^0 = 1），可以构造一个公差 d = p^(k-1) 的等差数列。

换句话说，第 i 项的次数为 (p^k)(p-1)。

注意到，所有 p^k 次割圆多项式都有 p 项，并且最后一项都为 1。

基于此，我们可以通过两种算法求解这个问题。
一是暴力求解（这是我当初的做法，非常地绕，建议看第二种解法），用 Miller-Rabin 筛出 p^k 对应的素数 p，再暴力找出展开式的第一项的次数。我们要寻找这样一个数，使得存在第一项次数 n_i ，使得存在等式 p^k ÷ n_i = p，再基于我们的等差数列理论，输出第 j 项的次数 n_i - j (p^(k-1))，即可输出正确答案，注意特判 x^0。

代码中 int solve(int n) 表示用 Miller-Rabin 算法筛出 n = p^k 中的素数 p。下同。

namespace st2{
        void calc(int n){
                int x = n*(solve(n)-1);
                // 规律：xi的次数总为 n*(p-1)
            bool first=true;
            int firsta=-1;
                for(int ni=n-1;ni>=1;ni--){
                        if(x / ni == solve(n) && first){
                                firsta=ni;
                        first=false;
                        }
                }
            for(int i=firsta;i>0;i-=(n/solve(n))){
                    printf("x^%d+",i);
            }
            printf("1");
        }
} 

基于该解法，我们可以移项等式，求得 n_i 其实就为 p^k - p^(k-1)，以此为第一项，输出第 j 项的次数 p^k - p^(k-1) - j (p^(k-1))，就是最后的结果，依旧注意特判 x^0.

namespace st2{
        void calc(int n){
        for(int i=n-n/solve(n);i>0;i-=(n/solve(n))){
            printf("x^%d+",i);
        }
        printf("1");
        }
}

另留一道作业（？）。

作业 （洛谷 · P1520）给定正整数 n，试求在整多项式环内对多项式 (x^n)-1 作因式分解，要求分解到全部为素多项式为止（即最后结果不能有可继续分解的多项式）。
提示 (x^n)-1 / (x+1) =

0x02 参考致谢 & 拓展阅读

本文在编写过程中参考了以下学术内容，在此一并表示感谢。

• 分圆域,Wikipedia,<https://en.wikipedia.org/wiki/Cyclotomic_polynomial#Examples>,.
• 分圆多项式和分圆域,小时百科,<https://wuli.wiki/online/Cycltm.html>.JierPeter,int256,.
• P1520 因式分解,洛谷,abcwuhang,<https://www.luogu.com.cn/problem/P1520>,.
• iridOI 2024 部分题目,iridOI,<https://www.luogu.com.cn/team/76764>,2024.
• 分圆多项式整理,_HofFen,<https://www.cnblogs.com/AllWeKnow/p/13518485.html>,2020.8.17.

如有部分内容侵权，请联系我进行删除，谢谢。