网络赛II Exponent题解
题意
给定n,求
其中ord(i)指的是i在模n意义下的阶,也就是满足
的最小x,不存在则为0
要做出这道题,需要三大块前置知识 : 卷积,群论,CRT(中国剩余定理)
卷积知识看我之前法的卷积博客,这里不过多讲解
传送门:卷积学习笔记
前置知识讲解1
群论的基本知识这里不赘述了,大学离散数学默认你学过了,这里只讲解一下群的阶
群的阶
首先定义群的阶为群的大小(元素个数),记为|G|
比如循环四元群的阶大小就是4
元素的阶
元素的阶就是ord(i)
根据拉格朗日定理可知,ord(i) | |G|
此外,ord(i)的倍数x都满足:
这个看似废话的性质(设为性质1)正是后面转化的第一步
此外,若考虑的模n整数乘法群(所有与n互质的数构成的群),像题目中的这种的话,会有更多性质
首先这个循环群的阶显然等于$\varphi(n)$,因为定义告诉我们是所有互质的数构成的
因为ord(i) | |G|,并且ord(i)的倍数依然有效,所以所有的元素的阶小于$\varphi(n)$,并且是其一个因数
到这里,我们就能进行我们的第一步转化了
转化1
因为要求的是
那么我们可以根据ord(i)来分类,统计其数量在乘以值
设:
其中#表示元素个数
所以转化为:
接下来,再设:
显然,满足d|m的A(d),都满足F(m)的要求(上文性质1),所以得到:
然后两边同时卷上$\mu$,也就是进行一下莫反(熟悉莫反的请自动忽略以下步骤)
(注意此处的m已经不是原来的m了,卷积后带入的是d)
所以原式:
接下来依旧是尝试交换求和顺序,如果改成先计算F(m),再看m被计算的次数.因此交换求和顺序的第一步应该得到:
接下来设d=mk,所以
补充知识讲解2
关键式子:
其中p是M的素因子
要证明这个式子成立,依旧先证明这个是一个积性函数
设f(M)等于上述式子,再假设gcd(a,b)=1,所以ab的因数可以被唯一的写成a的因数d1和b的因数d2的乘积
所以
而ab互质,所以d1和d2互质,所以可以使用$\mu$的积性的性质,化简为:
因此是积性函数
当$M=p^e$时
所以可以拆分n,然后再乘起来就行了,因此原式成立,这个也是莫比乌斯函数最重要的应用之一
计算F(m)
根据补充的这一个转化,原式可以进一步变形为:
那么可以发现的是,上述式子中值剩下一个F(m)是计算困难的了
接下来考虑怎么计算F(m)就行了
看一下F(m)的定义:
为了计算F(m),这里就不得不学习一下CRT(中国剩余定理)了
补充知识讲解3
中国剩余定理,用于解长这个样子的同余方程:
此处,如果几个n互质,那么x是由唯一解的
换句话说,如果后面的模数是互质的,那么只要知道了余数A数组,就能唯一确定一个数;反过来,要是给定一个数,他对应的余数也是唯一确定的
因为$x^m\equiv1 \ (\ mod \ n\ )$,所以$n|x^m-1$,而n可以被拆分成为多个质数的乘积,所以$p_i^{e_j}|x^m-1$,也就是$x^m\equiv1 \ (\ mod \ p_i^{e_j}\ )$
而中国剩余定理告诉我们,只要知道余数就能确定唯一的x,所以我们只要知道有多少组余数解就行了
因此,只要知道满足单个方程的解的数量,全部乘在一起就是F(m)了
小例子
比如n=15,m=2时,
群G={1,2,4,7,8,11,13,14}
15可以被拆成3和5,接下来列出余数表:
| num | mod 3 | mod 5 | pair |
|---|---|---|---|
| 1 | 1 | 1 | 1,1 |
| 2 | 2 | 2 | 2,2 |
| 4 | 1 | 4 | 1,4 |
| 7 | 1 | 2 | 1,2 |
| 8 | 2 | 3 | 2,3 |
| 11 | 2 | 1 | 2,1 |
| 13 | 1 | 3 | 1,3 |
| 14 | 2 | 4 | 2,4 |
mod 3能取到的值是{1,2},而mod 5能取到的值是{1,2,3,4},根据表格显然数字和余数是一一对应的
再定义$F_n(m)$为在mod n意义下F(m)的值
根据刚刚的结论,要求$F_{15}(2)$,那么就要先求$F_3(2)$和$F_5(2)$,这两个分别是2=#{1,2}和2=#{1,4},所以有四个,根据上面的表,倒推出是{1,4,11,14}
继续分析F(m)
根据上面的分析,得到的结论是
额,也就是依旧先证明积性函数,然后下面显然要计算只含一个质数的函数值了(这套逻辑学习卷积的时候应该是非常熟悉了吧)
首先,当$n=p_j^{e_j}$时,可以得到这个群的阶大小是$\varphi(n)=p^{e-1}(p-1)$
奇素数
当p为奇素数时,整个群是一个循环群,这意味着可以按循环群的性质来处理
假设这个循环群的生成元是g,那么这个群里的每个数字显然都能被$g^k$次表达
因此满足
设阶$\varphi(n)=N$,因为g的阶是N,那么
再设d=gcd(m,N),给上述式子两边同时除以d得到:
在1-N中,满足要求的k显然有d个,所以单个方程解的数量是gcd(m,N)
p=2
这个需要特殊讨论,因为当p=2,e>2时,这个群将不是一个循环群,必须额外讨论(怎么这么坏)
比如n=8,这个时候群为{1,3,5,7},{1,3}自己循环上了,整体却转不起来
从小的开始计算:
当e<=2时 : 可以套用循环群的公式
当e>2时:
此时群中的每个数字都能被唯一的表示为
所以要满足方程也就是要满足
那么和前面中国剩余定理分解的过程差不多,只要求出a的数量和b的数量就行了
也就是求出满足
的a的数量,以及
的b的数量
而这两者在模$2^e$下又分别是循环群,其中,-1的阶是2,5的阶是$2^{e-2}$,可以套循环群公式
总公式
综上
优化计算实现
注意到原本使用的是$\varphi(n)$,这个范围太大了,可以缩小一点,这里可以引入卡米歇尔函数加速计算
卡米歇尔函数其实就是所有阶的最小公倍数,记作$\lambda(n)$,这个也是有计算公式的
所以到此整题结束,参考代码:(使用了一些我常用的宏定义)
1 | ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} |
要是有更好的解释方式或者有错误之处,欢迎指出