杂题

题意

给定质数(p)，及长度为(n)的序列({a_i})
定义(f(x,y))为最小的正整数(i)使得(exists j,x^iequiv y^j(mod~p))
求(sumlimits_{i=1}^nsumlimits_{j=1}^n f(a_i,a_j) imes f(a_j,a_i)(mod~p))
(nle 10^5,ple 10^{18})

做法

令(g)为(p)的原根，令(x)为使得(g^xequiv a)
对于(a^{ord(a)}equiv 1)，有(g^{ord(a)x}equiv 1)。故(p-1|ord(a)x)，得到(frac{p-1}{(p-1,x)}|ord(a))，所以有(ord(a)=frac{p-1}{(p-1,x)})

令(x,y)分别使得(g^xequiv a,g^yequiv b)
对于(a^iequiv b^j)，有(g^{ix}equiv g^{jy})，那么(ixequiv jy(mod~p-1))。
根据裴蜀定理有((y,p-1)|ix)，(frac{(y,p-1)}{(y,p-1,x)}|i)，最小的(i)为(frac{(y,p-1)}{(y,p-1,x)})
由于(ord(a)=frac{p-1}{(p-1,x)})，可以看到((p-1,x)=frac{p-1}{ord(a)})，故(i=frac{frac{p-1}{ord(b)}}{(frac{p-1}{ord(a)},frac{p-1}{ord(b)})}=frac{ord(a)}{(ord(a),ord(b))})
(f(a_i,a_j)f(a_j,a_i)=frac{ord(a_i)ord(a_j)}{(ord(a_i),ord(a_j))^2})

由于(p)为质数，可通过试除法得到(ord(a))
在对(p)质因数分解后，可以通过莫比乌斯变换及莫比乌斯反演（高维前缀和）处理

题外话

大概是我题做得太少了？感觉这题很有趣w