题意:给定n个数a1,a2····an,依次求出相邻两个数值和,将得到一个新数列,重复上述操作,最后结果将变为一个数,问这个数除以m的余数与那些数无关?例如n=3,m=2时,第一次得到a1+a2,a2+a3,在求和得a1+2*a2+a3,它除以2的余数和a2无关。1<=n<=10^5, 2<=m<=10^9

分析:

通过试验可以发现,本题等价于求解C(n-1,i)的组合数中有哪些是m的倍数,可以利用唯一分解定理来判断:事先分解m,随后利用递推式计算每一项中包含m的素因数的指数即可。

代码如下:

//
//Created by BLUEBUFF 2016/1/11
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
//#include <bits/stdc++.h>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 100010;
const int maxm = 1e5+5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const int rev = (mod + 1) >> 1; // FWT
//const double PI = acos(-1);
//head
int fac1[100][2]; //fac[i][0]存放素因数, fac[i][1]存放其指数
int fac2[100], a[maxn];
void factor(int m){
    int &num = fac1[0][0];//fac[0][0]是表头,存放总的个数,用引用比较方便
    num = 0;
    for(int i = 2; i * i <= m; i++){
        if(m % i == 0){
            fac1[++num][0] = i;
            fac1[num][1] = 0;
            do{
                fac1[num][1]++;
                m /= i;
            }while(m % i == 0); //将i除干净
        }
    }
    if(m > 1)//如果分解到最后m仍然大于1,说明它是一个素数。注意:如果只是判断素因子有哪些,可以没有此处判断,否则必须有此步
    {
        fac1[++num][0] = m;
        fac1[num][1] = 1;
    }
}

bool check(int n, int j)//按照递推公式来计算第j项,检查唯一分解式的指数
{
    int num = fac1[0][0];
    int a = n - j, b = j;
    for(int i = 1; i <= num; i++){
        int p = fac1[i][0];
        int &q = fac2[i];
        for(; a % p == 0; a /= p, q++);//为了提高效率,只用检验m的分解式中的素因数即可
        for(; b % p == 0; b /= p, q--);
    }
    for(int i = 1; i <= num; i++){
        if(fac1[i][1] > fac2[i]){
            return false;
        }
    }
    return true;
}

int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        int cnt = 0;
        factor(m);
        memset(fac2, 0, sizeof(fac2));
        for(int i = 1; i < n; i++){
            if(check(n, i)){
                a[cnt++] = i + 1;
            }
        }
        printf("%d\n", cnt);
        for(int i = 0; i < cnt; i++){
            printf("%d%c", a[i], i == (cnt - 1) ? '\n' : ' ');
        }
    }
    return 0;
}