P12011 【MX-X10-T7】[LSOT-4] 春开，意遥遥。

· · 题解

思路：

题意看起来很抽象啊，先考虑求整体的答案。

考虑给这个新定义转化一下：

(a, b) \times (x, y) = (xb + ay, xa + by)

发现右边就是左边两两乘积组合出来的，于是右边的数的和是 (a + b)(x + y)，考虑右边两项的差是 (x - y)(b - a)，这个形式不太对称，于是后项减前项的差就是 (y - x)(b - a)。

于是想到一个对 (x, y) 用 (x + y, y - x) 来映射（在 p > 2 时显然是一一对应的），那么：

(a, b) \times (x, y) = (ax, by)

然后来考虑原来相等的定义 ay \equiv bx \pmod p，映射后就是：

(a - b)(x + y) \equiv (a + b)(x - y) \pmod p

你展开后发现还是原来一样的：

ay \equiv bx \pmod p

那么考虑固定的 b，其对应的权值是：

\left(\prod_{i = 1}^n x_i^{b_i}, \prod_{i = 1}^n y_i^{b_i} \right)

若两组 b, b' 的权值相同，那么要满足：

\prod_{i = 1}^n x_i^{b_i} \prod_{i = 1}^n y_i^{b'_i} \equiv \prod_{i = 1}^n y_i^{b_i} \prod_{i = 1}^n x_i^{b'_i} \pmod p

那么显然，若 x_i, y_i 中有一个是 0，那么 b 一定等于 b'，于是答案是 1；否则：

\prod_{i = 1}^n x_i^{b_i - b'_i} \equiv \prod_{i = 1}^n y_i^{b_i - b'_i} \pmod p

这种底数不相同的不好处理，你考虑找一个 p 的原根 g（对于 p = 2 没有原根，需要特判），将 x_i, y_i 都表示成 g^{x'_i}, g^{y'_i} 同余；于是相同等价于：

g^{\sum\limits_{i = 1}^n x'_i(b_i - b'_i)} \equiv g^{\sum\limits_{i = 1}^n y'_i (b_i - b'_i)} \pmod p

即：

\sum\limits_{i = 1}^n (x'_i - y_i')(b_i - b'_i) \equiv 0 \pmod {p - 1}

方便设 h_i = x'_i - y'_i，于是相同就是：

\sum_{i = 1}^n h_i b_i \equiv \sum_{i = 1}^n h_i b'_i \pmod{p - 1}

于是选最多不同的权值的 b，等价于求 \sum_{i = 1}^n h_i b_i \bmod (p -1) 能构成的数的数量，这就是裴蜀定理，只能构成 \gcd(h_1, \cdots, h_n, p - 1) 的倍数，于是答案是：

\frac{p - 1}{\gcd(h_1, \cdots, h_n, p - 1)}

但是你发现 p 很大，快速求离散对数是不现实的；但是你实际上不需要算离散对数真实的值，只需要算 \gcd(h_i, p - 1)。

于是根据阶的性质，你发现有：

\frac{x_i}{y_i} \equiv g^{x'_i - y'_i} \equiv g^{h_i} \pmod p

那么（阶的相关证明可以看 this）：

\delta_p(\frac{x_i}{y_i}) = \delta_p(g^{h_i}) = \frac{\delta_p(g)}{\gcd(\delta_p(g), h_i)} = \frac{p - 1}{\gcd(h_i, p - 1)}

于是：

\gcd(h_i, p - 1) = \frac{p - 1}{\delta_p(\frac{x_i}{y_i})}

这里令 A_i = \frac{p - 1}{\delta_p(\frac{x_i}{y_i})}，那么答案是：

\frac{p - 1}{\gcd(A_1, \cdots, A_n)}

你依次考虑每个质因子的贡献，显然上式子也等于：

\operatorname{lcm}(A_1, \cdots, A_n)

于是问题转化为给定序列 A，求所有自区间的 \operatorname{lcm} 之和；这是简单的，对于一个固定的左端点，右端点变化的次数只有 \log 次；于是可以扫右端点，每个点维护 p_l 表示到当前右端点的贡献，每次暴力往左边扫更新，如果更新后不变，那么更前面的也不会变了，所以停下。

需要注意一下，若当前右端点扫到的 i 的 (x_i, y_i) 有一个是 0，那么所有 h 都要变成 1；可以通过打懒标记实现。

还有提一下怎么快速算一个数的阶：

因为 \delta_p(x) \mid (p - 1)，且所有满足 x^a \equiv 1 的 a 都是 \delta_p(x) 的倍数；于是可以考虑倒着从 now = p - 1 开始，依次考虑每个质因子 v，判断 \frac{now}{v} 是否满足，不满足就扔掉 now \gets \frac{now}{v}，否则保留。

需要先根号的质因数分解，然后单次查询是 \log^2 p 的。

最后特判 p = 2 的情况：

首先一个区间至少有一个答案 b = 1；考虑 (1, 0)^2 = (0, 1), (0, 1)^2 = (0, 1), (1, 1)^2 = (0, 0)^2 = (0, 0)；所以若区间内包含 (1, 0) 且全是 (0, 1) 和 (1, 0) 那么 b = 2 也是合法的（注意这里是没有映射的）。

最后总复杂度应该是 O(\sqrt{p} + n \log^2 p)。

顺便拿下最优解。

完整代码：

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5 + 10, mod = 1e9 + 7;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
ll p;
int n, ans, cnt, sum;
int num[N];
ll h[N], pri[N], x[N], y[N], A[N];
bool vis[N];
inline ll qpow(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b & 1)
            ans = (__) ans * a % p;
        a = (__) a * a % p;
        b >>= 1;
    }
    return ans;
}
inline void init(ll n){
    for(ll i = 2; i * i <= n; ++i){
        if(n % i == 0){
            pri[++cnt] = i;
            while(n % i == 0){
                ++num[cnt];
                n /= i;
            }
        }
    }
    if(n > 1){
        pri[++cnt] = n;
        num[cnt] = 1;
    }
}
inline ll ask(ll x){
    ll now = p - 1;
    for(int i = 1; i <= cnt; ++i){
        for(int j = 1; j <= num[i]; ++j){
            if(qpow(x, now / pri[i]) == 1)
              now /= pri[i];
            else
              break;
        }
    }
    return now;
}
int main(){
    n = read(), p = read();
    if(p == 2){
        ans = (1ll * n * (n + 1) >> 1) % mod;
        int pre = 0, lst = 0;
        for(int i = 1; i <= n; ++i){
            int x = read(), y = read();
            if(x && !y)
              lst = i;
            if(x == y)
              pre = i;
            ans = (ans + max(lst - pre, 0)) % mod;
        }
        write(ans);
        putchar('\n');
        return 0;
    }
    init(p - 1);
    for(int i = 1; i <= n; ++i){
        ll a = read(), b = read();
        x[i] = (a + b) % p;
        y[i] = (b - a + p) % p;
        if(!x[i] || !y[i])
          vis[i] = 1;
        else
          A[i] = ask((__)x[i] * qpow(y[i], p - 2) % p);
    }
//  for(int i = 1; i <= n; ++i)
//    cerr << A[i] << ' ';
//  cerr << '\n';
    for(int r = 1; r <= n; ++r){
        if(vis[r])
          sum = r;
        else{
            h[r] = A[r];
            for(int l = r - 1; l >= 1; --l){
                if(vis[l])
                  break;
                ll t = __gcd(h[l], A[r]);
                if(t == A[r])
                  break;
                sum = (sum - h[l] % mod + mod) % mod;
                h[l] = h[l] / t * A[r];
                sum = (sum + h[l] % mod + mod) % mod;
            }
            sum = (sum + h[r] % mod) % mod;
        }
        ans = (ans + sum) % mod;
    }
//  for(int l = 1; l <= n; ++l){
//      ll now = 0;
//      for(int r = l; r <= n; ++r){
//          if(vis[r]){
//              ans = (ans + (n - r + 1)) % mod;
//              break;
//          }
//          if(!now)
//            now = A[r];
//          else
//            now = now / __gcd(now, A[r]) * A[r];
//          ans = (ans + now % mod) % mod;
//      }
//  }
    write(ans);
    return 0;
}