UVA1635-唯一分解定理的基本应用2

这是一个极其典型的“从素因子角度出发”的题目，下面是我的代码：
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 const int maxn = 1e5 + 10;
 9 int md[100],mz[100];
10 int ans[maxn];
11 int n,m,lenth;
12 int c[100];
13 
14 bool check(int n,int i)
15 {
16     int x=n-i;
17     int y=i;
18     for(int k=0;k<lenth;k++)
19     {
20         int p=md[k];
21         while(x%p==0)
22         {
23             x/=p;
24             c[k]++;
25         }
26         while(y%p==0)
27         {
28             y/=p;
29             c[k]--;
30         }//上下两个循环不能合并,因为这是一个递增积累过程,
31     }//也正因如此才需要额外开辟一个数组c.
32     for(int k=0;k<lenth;k++)
33         if(c[k]<mz[k])return false;
34     return true;
35 }
36 
37 int factor()
38 {//用来分解m
39     memset(md,0,sizeof(md));
40     memset(mz,0,sizeof(mz));
41     int c=m,cur=0;
42     int p=sqrt(c);
43     for(int i=2;i<=p;i++)
44     {
45         bool ok=false;
46         while(c%i==0)
47         {
48             md[cur]=i;
49             mz[cur]++;
50             c/=i;
51             ok=true;
52         }
53         if(ok)cur++;
54         if(c==1)break;
55     }
56     if(c>1)md[cur]=c,mz[cur]=1,cur++;
57     return cur;
58 }
59 
60 int main()
61 {
62     //freopen("input.txt","r",stdin);
63     //freopen("text.txt","w",stdout);
64     while(cin>>n>>m)
65     {
66         lenth=factor();//一开始忘记了记录lenth
67         int cnt=0;
68         memset(c,0,sizeof(c));
69         //
70         for(int i=1;i<n-1;i++)
71             if(check(n,i))ans[cnt++]=i+1;
72         printf("%d
",cnt);
73         for(int i=0;i<cnt;i++)
74         {
75             if(i>0)printf(" ");
76             printf("%d",ans[i]);
77         }
78         printf("
");
79     }
80     return 0;
81 }