at_abc335_g 题解

· · 题解

Solution

标题上面说了这是离散对数问题。于是我们不妨找出原根，然后用 BSGS 求出每个数的离散对数。这样等价于 k \log a_i \equiv \log a_j \pmod {p-1}。考虑 (\log a_i,p-1)=d，那么等价于 d \mid \log a_j。而这个实际上等价于 d \mid (p-1,\log a_j)。于是令 b_j = (p-1,\log a_j)。我们只需统计 1 \le i < j \le n 且 b_i \mid b_j。的数量。不妨将 p-1 质因数分解，这样很容易比较快速的找到 b_j 的所有因数。（事实上，所有的 b 只有 d(p-1) \le 1.1 \times 10^4 种情况。很容易找所有倍数关系，而这种倍数关系显然不是很密集。）

但是很遗憾，BSGS 是复杂度是错的。于是我们考虑求出每个数对 p 的阶，假设这是 t，那么说明 t \log a_i \equiv 0 \pmod {p-1}，显然有 t = \dfrac{p-1}{(p-1,\log a_i)}。

然后考虑怎么求阶。我们枚举 p-1 的每个素因子，看能不能除掉即可。

这样你最多进行 O(n\log^2 p) 次乘法操作。我也许感觉能过。如果假了别嘲笑我。

好它过了。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,p,a[MAXN];
int qpow(__int128 base,int p,int mod) {
    __int128 ans=1;
    while(p) {
        if(p&1) ans=ans*base%mod;
        base=base*base%mod,p>>=1;   
    }
    return ans;
}
vector<int> frac;
map<int,int> mp;
int calc_b(int v) {
    int ans=p-1;
    for(auto id:frac) if(qpow(v,ans/id,p)==1) ans/=id;
    return (p-1)/ans;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>p; ffor(i,1,n) cin>>a[i];
    int v=p-1;
    ffor(i,2,v/i) while(v%i==0) frac.push_back(i),v/=i;
    if(v) frac.push_back(v);
    sort(frac.begin(),frac.end());
    ffor(i,1,n) mp[calc_b(a[i])]++;
    int ans=0;
    for(auto pr1:mp) for(auto pr2:mp) if(pr1.first%pr2.first==0) ans+=pr1.second*pr2.second;
    cout<<ans;
    return 0;
}