记录编号	237347	评测结果	AAAAAAAAAA
题目名称	2180.无关的数	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.154 s
提交时间	2016-03-16 22:41:16	内存使用	0.28 MiB

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
LL n, m;
LL gcd(LL a, LL b) {
	return b == 0 ?  a : gcd(b, a%b);
} 
vector<LL> sol;
LL up, down;
void handle1(LL x) {
	LL tmp = gcd(x, m); 
	while(tmp != 1 && x != 1) {//tmp == 1 意味着两个数没有最大公约数 
		up *= tmp;
		x /= tmp;
		tmp = gcd(x, m);
	}
}
void handle2(LL x) {
	LL tmp = gcd(x, m);
	while(tmp != 1 && x != 1) {
		down *= tmp;
		x /= tmp;
		tmp = gcd(x, m);
	}
}
int main() {
	freopen("irre.in", "r", stdin);
	freopen("irre.out", "w", stdout); 
	scanf("%lld %lld", &n, &m);//要求第n行的数，其实是求c(n-1, i)  
	//即对于n的第2~n/2位处理，如9,2=> c(8,1) 9,3=>c(8,2) 
	up = 1; down = 1;
	LL tmp;
	for(LL i = 2; i < n; i++) {//从第2到第n-1 n,i c(n-1, i-1)
		handle1(n-i+1);
		handle2(i-1);
		tmp = gcd(up, down);
		while(tmp != 1 && up != 1 && down != 1) {
			up /= tmp;
			down /= tmp;
			tmp = gcd(up, down);
		} 
		if(gcd(up, m) == m) {
			sol.push_back(i);
		}
	}
	printf("%d\n",sol.size());
	for(LL i = 0 ; i < sol.size(); i++) {
		printf("%lld ",sol[i]);
	} 
	return 0;
}