提出 #73500532

---

ソースコード 拡げる

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_M = 1000;
int M, A, B;
// 0:未检测, 1:合法, 2:不合法
int status[MAX_M][MAX_M];
// 标记当前DFS路径中的状态（检测循环）
bool in_path[MAX_M][MAX_M];

// 计算 (a % mod)，确保结果非负
inline int mod(int a, int mod) {
    return (a % mod + mod) % mod;
}

// 检测状态(x,y)是否合法，返回true=合法，false=不合法
bool check(int x, int y) {
    // 初始状态含0 → 不合法
    if (x == 0 || y == 0) {
        status[x][y] = 2;
        return false;
    }
    // 已检测过，直接返回结果
    if (status[x][y] != 0) {
        return status[x][y] == 1;
    }
    // 路径中重复出现 → 进入循环且无0，合法
    if (in_path[x][y]) {
        status[x][y] = 1;
        return true;
    }

    in_path[x][y] = true; // 标记进入当前路径

    // 计算下一个状态（严格保证非负）
    long long next = 1LL * A * y + 1LL * B * x;
    int ny = mod(next, M);
    int nx = y;

    // 下一个状态的y是0 → 当前状态不合法
    bool valid = true;
    if (ny == 0) {
        valid = false;
    } else {
        // 递归检测下一个状态
        valid = check(nx, ny);
    }

    in_path[x][y] = false; // 回溯，取消路径标记
    // 记忆当前状态结果
    status[x][y] = valid ? 1 : 2;
    return valid;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> M >> A >> B;

    // 初始化状态数组
    memset(status, 0, sizeof(status));
    memset(in_path, 0, sizeof(in_path));

    int ans = 0;
    // 遍历所有可能的(x,y)对
    for (int x = 0; x < M; ++x) {
        for (int y = 0; y < M; ++y) {
            if (check(x, y)) {
                ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

提出情報

ジャッジ結果