这种题目最重要的是思路了清晰
1 #include <cstdio> 2 #include <cstring> 3 const int maxn = 100005;//sqrt(n)+1 is enough 4 5 int fac[100][2]; 6 int fac_c[100]; 7 int a[maxn]; 8 void factor(int m) { 9 int& num = fac[0][0]; 10 num = 0; 11 for (int i = 2; i*i <= m; i++) { 12 if(m%i == 0) { 13 fac[++num][0] = i; 14 fac[num][1] = 0; 15 do { 16 fac[num][1]++; 17 m/= i; 18 } while(m%i == 0); 19 } 20 } 21 if (m > 1) { 22 fac[++num][0] = m; 23 fac[num][1] = 1; 24 } 25 } 26 bool check(int n, int j) { 27 int num = fac[0][0]; 28 int a = n - j; 29 int b = j; 30 for (int i = 1; i <= num; i++) { 31 //为了提高效率，只用检验m的分解式中的素因数 32 int p = fac[i][0]; 33 int& q = fac_c[i]; 34 for (; a%p == 0; a/=p, q++); 35 for (; b%p == 0; b/=p, q--); 36 } 37 for (int i = 1; i <= num; i++) { 38 if (fac[i][1] > fac_c[i]) { 39 return false; 40 } 41 } 42 return true; 43 } 44 int main(void) { 45 int n, m; 46 for (; scanf("%d%d", &n, &m)==2;printf(" ")) { 47 int cnt = 0; 48 factor(m); 49 memset(fac_c, 0, sizeof(fac_c)); 50 for (int i = 1; i < n; i++) { 51 if (check(n, i)) { 52 a[cnt++] = i+1; 53 } 54 } 55 printf("%d ", cnt); 56 for (int i = 0; i < cnt; i++) { 57 printf("%s%d",i==0?"":" ", a[i]); 58 } 59 } 60 return 0; 61 }