题意分析

年轻的密码分析师乔治发明了一种新的随机整数生成方案，用于生成范围在 0 到 m - 1 的随机数。该方案首先生成 n 个 0 到 m - 1 的随机整数 $a_1, a_2, \ldots, a_n$，然后通过不断计算相邻数字的和并替换原数组，直到只剩下一个数字，最后将该数字对 m 取模作为生成结果。乔治发现该方案存在问题，某些初始生成的数字不影响最终结果，他将这类数字称为不相关元素。题目要求根据输入的 n 和 m（1 <= n <= 100 000，2 <= m <= 10^9），找出初始数组中不相关元素的数量，并输出这些不相关元素的下标（下标按升序排列，以空格分隔）。

问题核心

本题的核心在于分析乔治的随机数生成过程，找出哪些初始数组元素在经过一系列求和与取模操作后，对最终结果没有影响。这需要理解生成过程中每个元素的变化规律以及它们如何影响最终结果，关键在于确定每个元素在最终结果表达式中的系数情况。如果某个元素的系数在模 m 意义下为 0，那么该元素就是不相关元素。

解题思路

二项式系数法： 可以发现，在最终结果的计算过程中，每个初始元素 $a_i$ 的系数符合二项式系数的规律。根据组合数学知识，从 n 个元素开始，经过一系列操作后， $a_i$ 的系数为 $C_{n - 1}^{i - 1}$（其中 $C_{n}^{k}$ 表示从 $n$ 个元素中选取 $k$ 个元素的组合数）。 计算每个二项式系数 $C_{n - 1}^{i - 1}$ ，并对 m 取模。如果取模结果为 0 ，则说明 $a_i$ 是不相关元素。 计算二项式系数时，可以利用组合数的递推公式 $C_{n}^{k}=C_{n - 1}^{k - 1}+C_{n - 1}^{k}$ ，结合取模运算进行高效计算。

优化计算： 由于 $n$ 的范围较大（1 <= n <= 100 000），直接计算二项式系数可能会导致溢出或效率低下。可以使用卢卡斯定理（Lucas's Theorem）来优化计算。卢卡斯定理指出，对于非负整数 $n$ 和 $k$ 以及素数 $m$ ，有 $C_{n}^{k}\equiv\prod_{i = 0}^{s}C_{n_i}^{k_i}\pmod{m}$ ，其中 $n$ 和 $k$ 在 $m$ 进制下分别表示为 $n = n_sm^s+\cdots + n_1m + n_0$， $k = k_sm^s+\cdots + k_1m + k_0$ 。对于非素数 $m$ ，可以先对 $m$ 进行质因数分解，然后利用中国剩余定理（Chinese Remainder Theorem）分别计算在每个质因数模下的结果，再合并得到最终结果。

统计与输出： 遍历所有的初始元素，按照上述方法判断每个元素是否为不相关元素，并统计不相关元素的数量。 将不相关元素的下标按升序排列后输出，同时输出不相关元素的总数。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> factorize(int m) {
    vector<pair<int, int>> factors;
    for (int i = 2; i * i <= m; ++i) {
        if (m % i == 0) {
            int cnt = 0;
            while (m % i == 0) {
                cnt++;
                m /= i;
            }
            factors.emplace_back(i, cnt);
        }
    }
    if (m > 1) {
        factors.emplace_back(m, 1);
    }
    return factors;
}

bool is_irrelevant(int k, int n_minus_1, const vector<pair<int, int>>& factors) {
    for (auto [p, e] : factors) {
        int cnt = 0;
        long long pow_p = p;
        while (pow_p <= n_minus_1) {
            cnt += (n_minus_1 / pow_p) - (k / pow_p) - ((n_minus_1 - k) / pow_p);
            if (cnt >= e) {
                break;
            }
            pow_p *= p;
        }
        if (cnt < e) {
            return false;
        }
    }
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> factors = factorize(m);
    vector<int> irrelevant;

    int n_minus_1 = n - 1;
    for (int k = 0; k < n; ++k) {
        if (is_irrelevant(k, n_minus_1, factors)) {
            irrelevant.push_back(k + 1);
        }
    }

    cout << irrelevant.size() << endl;
    if (!irrelevant.empty()) {
        for (size_t i = 0; i < irrelevant.size(); ++i) {
            if (i > 0) cout << " ";
            cout << irrelevant[i];
        }
        cout << endl;
    }

    return 0;
}