Irrelevant Elements UVA

很不错的一道题

//a^b=c a^c=b 
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<assert.h>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<sstream>
#include<stack>
#include<queue>
#include<string>
#include<bitset>
#include<algorithm>
#pragma warning(disable:4996)
#define me(s)  memset(s,0,sizeof(s))
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int dr[] = { 0, -1, 0, 1, -1, -1, 1, 1 };
const int dc[] = { -1, 0, 1, 0, -1, 1, -1, 1 };
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-15;
const int maxn = 100000 + 5;
int bad[maxn];
void prime_factoral(int n, vector<int>& primes)
{int m = sqrt(n) + 0.5;for (int i = 2; i <= m; i++) {if (n%i == 0) {primes.push_back(i);while (n%i == 0) n /= i;}}if (n > 1) primes.push_back(n);
}
int main()
{int n, m, kcase = 0;while (cin >> n >> m){vector<int>primes;prime_factoral(m, primes);me(bad);n--;for (int i = 0; i < primes.size(); i++) {int p = primes[i];int x = m, e = 0, min_e = 0;while (x%p == 0) {x /= p; min_e++;}for (int k = 1; k < n; k++) {x = n - k + 1;while (x%p == 0) {x /= p; e++;}x = k;while (x%p == 0) {x /= p; e--;}if (e < min_e) bad[k] = 1;}}vector<int>ans;for (int i = 1; i < n; i++) if (!bad[i]) ans.push_back(i + 1);printf("%d\n", ans.size());if (!ans.empty()) {printf("%d", ans[0]);for (int i = 1; i < ans.size(); i++) printf(" %d", ans[i]);}printf("\n");}
}