Multiple-Free Sequences の解説

(i % m, j % m)から遷移される状態はM^2しかないので前の状況を保存しつつでやれば全探索可能です。

あとは頑張れば答えでです。

fn main() {
    input! {
        m: usize, a: usize, b: usize
    }
    let mut ans: Vec<Vec<Option<bool>>> = vec![vec![None; m]; m];
    let mut visited = vec![vec![false; m]; m];
    let mut count = 0;
    for (x, y) in iproduct!(0..m, 0..m) {
        if let Some(v) = ans[x][y] {
            count += if !v { 1usize } else { 0 };
            continue;
        }
        let mut now = (x, y);
        let mut flg = false;
        let mut v = vec![];
        loop {
            let (s1, s2) = now;
            if visited[s1][s2] {
                let pre = ans[s1][s2].unwrap_or(false);
                flg = flg || pre || s1 % m == 0 || s2 % m == 0;
                break;
            }
            v.push(now);
            visited[s1][s2] = true;
            let ss1 = s2;
            let ss2 = (a * s2 + b * s1) % m;
            now = (ss1, ss2);
        }
        v.reverse();
        for &(x, y) in v.iter() {
            flg = flg || x % m == 0 || y % m == 0;
            ans[x][y] = Some(flg);
        }
        count += if !flg { 1usize } else { 0 };
    }
    println!("{}", count);
}