https://atcoder.jp/contests/abc335
G - Discrete Logarithm Problems
长度n数组a, 质数$p$
1
2
3
| for i in 1..n:
for j in 1..n:
ans += 存在k使得 ai.pow(k) \equiv aj \pmod{p}
|
求 ans
n 2e5
$p \in [2,10^{13}]$
$a_i \in [1,p)$
5s
1024mb
我的思路
首先什么时候会不存在不等
$a_i^k\equiv a_j\pmod{p}$
而注意到例如$1$ 只能得到$1$,而$p-1$只能得到$-1,1$
回忆到64位的miller robin 判别法的过程
需要考虑的是 幂次是$p-1$的 因子 的幂次,也就是$a^t\equiv 1 \pmod{p}$
例如对于7来说
1
2
3
4
5
6
| 1 (1)
2->4->1 (3)
3->2->6->4->5->1 (6, ntt中会选择的)
4->2->1 (3)
5->4->6->2->3->1 (6)
6->1 (2)
|
p有10^13，可以暴力 sqrt(p) 分解p-1
然后 通过从小到大尝试 p-1的因子的幂次 是否
可以O(n * log(p) * log(p))计算出每个 ai 的最小幂次x,使得ai^x = 1 \mod p
对于长度 p-1的 肯定是全 可以 贡献N
问题是 长度更小的呢，如何知道哪些可以，哪些不行
$t(a_i) =$最小的幂次使得$a_i^{t}\equiv 1\pmod p$
那么对于成立的 $a_i^k\equiv a_j\pmod{p}$
有$k\le t(a_i)$
$a_i^{kt(a_j)}\equiv a_j^{t(a_j)}\equiv 1\pmod{p}$
$kt(a_j) =wt(a_i), w\in\mathbb{Z}^+$
$\displaystyle k\frac{t(a_j)}{\gcd(t(a_j),t(a_i))} =w\frac{t(a_i)}{\gcd(t(a_j),t(a_i))}, w\in\mathbb{Z}$
$k$是$\displaystyle \frac{t(a_i)}{\gcd(t(a_j),t(a_i))}$的倍数 且 $\le t(a_i)$
好像量级还是没啥变化
另外$1\equiv (a_i^{t(a_i)})^k\equiv (a_i^{k})^{t(a_i)} \equiv a_j^{t(a_i)} \pmod{p}$
所以如果$t(a_j) > t(a_i)$ ,和t的最小的定义矛盾, 必定没有方案
所以$t(a_j)\le t(a_i)$
同样从幂次的因子角度考虑
3->2->6->4->5->1 长度6
而6的因子有1,2,3,6
例如 $2=3^2$,$2^t=3^{2t}$,所以2->4->1实际上是上面2的倍数项
例如 $6=3^3$,$6^t=3^{3t}$,所以6->1实际上是上面3的倍数项
所以$a_i^x$如果$x$是$t(a_i)$的因子,那么$t(a_i^x)\equiv \frac{t(a_i)}{x}$
而如果拉长
1
2
3
4
| [ ] [ ]
3->2->6->4->5->1->3->2->6->4->5->1
| | |
4 2 1
|
这里有$t(3^{len=4})=3=\frac{1}{2}6=\frac{1}{2}t(3)$
而 这种倍长过程实际就是在求$lcm(t(3),len=4)$
所以显然$t(a^x)=\frac{lcm(x,t(a))}{x}=\frac{t(a)}{\gcd(x,t(a))}$
$t(a_j)=t(a_i^k)=\frac{t(a_i)}{\gcd(k,t(a_i))}$
2和3都是6的因子不太好考虑不是的情况
现在考虑p=11,那么p-1=10,因子有1,2,5,10
1
2
3
| 2->4->8->5->10->9->7->3->6->1
pow 1 2 3 4 5 6 7 8 9 10
len 10 5 10 5 2 5 10 5 10 1
|
注意到1~10每个数字可以都表示成 2的幂次，所以, 它们的链，不过是2多次增长以后，按照幂次跳跃取得的
一个猜想:
长度成倍数，则包含：t(a_i) % t(a_j) =0则$a_i^k\equiv a_j\pmod{p}$
那么p=11也不是个好例子，看看p=13,p-1=12,这样的话长度可能是4和6,而4和6不是倍数关系却gcd不为1
1
2
3
4
5
6
| 2->4->8->3->6->12->11->9->5->10->7->1
pow 1 2 3 4 5 6 7 8 9 10 11 12
[1] 2 3 4 长度4的链
3 2 [1] 4 长度4的链
[1] 2 3 4 5 6 长度6的链
5 4 3 2 [1] 6 长度6的链
|
虽然有重叠元素，但是互相不包含,
对于oi比赛，那这个时候，已经可以编码了
那么问题来了，数学上如何证明呢？？？？？？
而且这样的方法 因子可能有8e3量级的个数, 在计算 t(a_i)时 时间似乎不够 2e5 * 8e3 * log(8e3,2) ~= 2e10
所以 数学证明 和 效率都有问题