AtCoder Beginner Contest 335 G

https://atcoder.jp/contests/abc335/tasks/abc335_g

となる最小のpをaの周期と呼ぶことにします。
だから、周期はP-1の約数になります。なので、P-1から割っていって1になる最小の約数を求めればよいですが、もうちょっと効率のよい方法がある気がするんですよね。
周期が求められればあとは簡単で、の周期をとすると、ある周期がP-1の元gに対して、とすると、でを割り切れるのと条件が同値です。なので、がで割り切れればよいです。
時間がけっこう厳しいです。mulが最初のバージョンより3倍速くなって通りました。i64を工夫してオーバーフローしないようにしましたが、i128を使った方がちょっと速かったです。

// Discrete Logarithm Problems
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn div_pow(n: i64, d: i64) -> (u32, i64) {
    let mut e: u32 = 0;
    let mut m = n;
    while m % d == 0 {
        e += 1;
        m /= d
    }
    (e, m)
}

fn factorize(n: i64, p0: i64) -> Vec<(i64, u32)> {
    if n == 1 {
        return vec![]
    }
    
    for p in p0.. {
        if p*p > n {
            return vec![(n, 1)]
        }
        else if n % p == 0 {
            let (e, m) = div_pow(n, p);
            let fs0 = factorize(m, p+1);
            let mut fs: Vec<(i64, u32)> = vec![(p, e)];
            fs.extend(fs0);
            return fs
        }
    }
    vec![(n, 1)]
}

fn mul(a: i64, b: i64, d: i64) -> i64 {
    
    let mut p: i64 = 0;
    let mut a = a;
    let mut b = b;
    while b > 0 {
        let b1 = b & ((1 << 15) - 1);
        p = (p + a * b1) % d;
        a = (a << 15) % d;
        b >>= 15
    }
    p
}

fn pow(b: i64, e: i64, d: i64) -> i64 {
    if e == 0 {
        1
    }
    else if e == 1 {
        b
    }
    else if e % 2 == 1 {
        mul(b, pow(b, e-1, d), d)
    }
    else {
        let p = pow(b, e/2, d);
        mul(p, p, d)
    }
}


//////////////////// process ////////////////////

fn read_input() -> (i64, Vec<i64>) {
    let v = read_vec();
    let P = v[1];
    let A = read_vec();
    (P, A)
}

fn period(a: i64, fs: &Vec<(i64, u32)>, P: i64) -> i64 {
    let mut n = P - 1;
    for &(p, e) in fs.iter() {
        for _ in 0..e {
            n /= p;
            if pow(a, n, P) != 1 {
                n *= p;
                break
            }
        }
    }
    n
}

fn F(P: i64, A: Vec<i64>) -> i64 {
    let fs = factorize(P-1, 2);
    let mut counter: HashMap<i64, i64> = HashMap::new();
    for a in A.into_iter() {
        let p = period(a, &fs, P);
        let e = counter.entry(p).or_insert(0);
        *e += 1
    }
    
    let mut s: i64 = 0;
    for (&p1, &n1) in counter.iter() {
        for (&p2, &n2) in counter.iter() {
            if p1 % p2 == 0 {
                s += n1 * n2
            }
        }
    }
    s
}

fn main() {
    let (P, A) = read_input();
    println!("{}", F(P, A))
}