UVA 1635 Irrelevant Elements——组合数+唯一分解定理

UVA 1635 Irrelevant Elements——组合数+唯一分解定理

#include #include #include #include #include using namespace std;const int maxn = 1e5+10;int n, m, num, prime[110][2], a[maxn], b[110];void fenjie() { for(int i = 2; i*i <= m; i++) { if(m % i == 0) { prime[++num][0] = i; prime[num][1] = 1; m /= i; while (m % i == 0) { prime[num][1]++; m /= i; } } } if(m > 1) { prime[++num][0] = m; prime[num][1] = 1; }}bool check(int i) { int x = n - i, y = i; for(int i = 1; i <= num; i++) { int p = prime[i][0]; while(x % p == 0) { x /= p; b[i]++; } while(y % p == 0) { y /= p; b[i]--; } } for(int i = 1; i <= num; i++) if (b[i] < prime[i][1]) return false; return true;}int main() { //freopen("out.txt", "w", stdout); while(~scanf("%d %d", &n, &m)) { num = 0; fenjie(); memset(b, 0, sizeof(b)); int cnt = 0; for(int i = 1; i < n-1; i++) if (check(i)) a[++cnt] = i + 1; printf("%d\n", cnt); for (int i = 1; i <= cnt; i++) { if (i != 1) printf(" "); printf("%d", a[i]); } printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。