Atcoder abc335

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
G(数论,原根)

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

所以 数学证明 和 效率都有问题

题解

一样 也先 $\sqrt{p}$计算$p-1$的因子

然后最小的$m$使得$x^m\equiv 1\pmod{p}$称作 order, m一定是p-1的因数

然后 方法是

1
2
3
4
m = p-1
for k = 1...n:
	while m%p[k] == 0 and x.pow(M/p[k]) == 1:
		M = M/p[k]

则 m为要求的幂次!!!!!!!

啊 好有道理!!!!!!!!!!!!!!!!!!!!!! 这反过来想很显然, 这样就不用枚举因数而是只需要枚举质因子了！！！

因为 如果$m \star \prod p_i^{t_i} = p-1$

$m \star \prod_{i\neq j} p_i^{t_i} | p-1$ 且 使得$a^{m \star \prod_{i\neq j} p_i^{t_i}}\equiv 1\pmod{p}$

这样 2e5 * log(8e3,2) * log(8e3,2) ~= 2e7 就能AC了

然后就是我猜到了，但没有证明的性质, $A_i^k\equiv A_j\pmod{p}$ 和$\frac{t(a_i)}{t(a_j)}\in\mathbb{Z}^+$

  1. 原根 存在性, p是质数,原根一定存在，见博客 算法NTT中的 原根存在性定理 中 素数p一定有原根

那么取原根p, 按照上面的 想法 任何数可以表示成 原根的幂次，而它的链 连接了所有和 gcd(p-1,幂次) 上的点

所以得证

atcoder官方有更公式化的证明

代码

https://atcoder.jp/contests/abc335/submissions/50109613

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll qpow(ll a,ll pwr,ll mod){
  __int128 r=1;
  __int128 b=a;
  while(pwr){
    if(pwr&1) (r*=b)%=mod; // overflow ?
    (b*=b)%=mod; // overflow ?
    pwr/=2;
  }
  return r;
}
ll read(){ll r;scanf("%lld",&r);return r;}
ll a[200010];
ll pwrs[200010];
int main(){
  int n=read();
  ll prime=read();
  rep(i,0,n) a[i]=read();
  vector<pair<ll,ll> > factors;
  ll q=prime-1;
  rep(i,2,q+1) {
    if(i*i > q) break;
    if(q%i==0) {
      int pwr = 0;
      while(q%i==0) {
        q/=i;
        pwr++;
      }
      factors.push_back({i,pwr});
    }
  }
  if(q!=1) factors.push_back({q,1});
  rep(i,0,n) { // 2e5 * log(8e3,2) * log(8e3,2) ~= 2e7
    ll x = prime-1;
    for(auto [f,pw]:factors) while(pw and qpow(a[i],x/f, prime) == 1) {
      x/=f;
      pw--;
    }
    pwrs[i] = x;
  }
  sort(pwrs,pwrs+n);
  vector<pair<ll,ll> > cnt;
  rep(i,0,n) {
    if(i==0 or pwrs[i] != pwrs[i-1]) {
      cnt.push_back({pwrs[i],1});
    }else{
      cnt.back().second++;
    }
  }
  ll ans = 0;
  for(auto [p0,c0]:cnt) for(auto [p1,c1]:cnt) if(p0%p1==0) ans += c0*c1;
  printf("%lld\n",ans);
  return 0;
}

总结

G: 这个结论还算显然好猜，对于oj来说不算难，但数学上自己证明起来还是有难度的

然后，不需要枚举因数啊，我好蠢，这里枚举质因子下降就可以了，哎这个结论反过来想很容易证明的（对于题目已经可以AC了）

这个后面的数学证明，能力还是不够，关键的缺失是在原根的存在性上，这个我更新了博客中 算法NTT中的原根的那段

光从oj上真算不上橙题，上面那个我没想出的枚举质因子，本身也不难，结论也好猜，难的是数学上从零的证明