uva 11728 Alternate Task

　　vjudge 上题目链接：uva 11728

　　其实是个数论水题，直接打表就行：

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 int ans[1003];
 6 inline void init(int n = 1000) {
 7     for(int i = 1; i <= n; ++i) {
 8         int sum = 0;
 9         for(int j = 1; j <= i; ++j)
10             if(i % j == 0)   sum += j;
11         if(sum <= 1000)   ans[sum] = i;
12     }
13 }
14 
15 int main() {
16     int s,Case = 0;
17     init();
18     while(~scanf("%d",&s),s)
19         printf("Case %d: %d
",++Case, !ans[s]? -1: ans[s]);
20     return 0;
21 }

　　可我一开始却杀鸡用了牛刀，想得超复杂，就因为大白书上提示"唯一分解定理，回溯"什么的，于是我就按着这样的思路去做了，结果写得超复杂，感觉过了也没有任何意义了。。。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 bool vis[1060];
 8 int pri[200];
 9 inline int init_pri(int n = 1050) {
10     int c = 0;
11     for(int i = 2; i <= n; ++i)
12         if(!vis[i]) {
13             pri[++c] = i;
14             for(int j = i << 1; j <= n; j += i)    vis[j] = 1;
15         }
16     return c;
17 }
18 
19 struct node {
20     int sum, p, r, pow;
21     node() {}
22     node(int sum, int p, int r, int pow): sum(sum), p(p), r(r), pow(pow) {}
23     bool operator < (const node & n2) const {
24         if(sum == n2.sum)   return p < n2.p;
25         return sum < n2.sum;
26     }
27     void print() const {
28         printf("sum = %d  p = %d  r = %d  pow = %d
",sum,p,r,pow);
29     }
30 };
31 
32 vector<node> fac;
33 
34 inline void init() {
35     init_pri();
36     for(int i = 1; pri[i] <= 1020; ++i) {
37         int sum = 1, mul = 1, len = 0;
38         while(sum <= 1020) {
39             mul *= pri[i];
40             sum += mul;
41             if(sum > 1020)  break;
42             fac.push_back(node(sum, pri[i], ++len, mul));
43         }
44     }
45     sort(fac.begin(), fac.end());
46 }
47 
48 int find(const vector<node> &c, int low, int up, int x) {
49     int mid;
50     while(low <= up) {
51         mid = low + up >> 1;
52         if(c[mid].sum == x)   return mid;
53         else if(x < c[mid].sum)    up = mid - 1;
54         else    low = mid + 1;
55     }
56     return low;
57 }
58 
59 int ans;
60 bool sign[1030];
61 
62 void dfs(int s, int id, int n) {
63     if(s == 1) {
64         if(n > ans)  ans = n;
65         return ;
66     }
67     if(s <= 0 || id < 0)   return ;
68     if(!sign[fac[id].p] && s % fac[id].sum == 0) {
69         sign[fac[id].p] = 1;
70         dfs(s / fac[id].sum, id - 1, n * fac[id].pow);
71         sign[fac[id].p] = 0;
72     }
73     dfs(s, id - 1, n);
74 }
75 
76 int main() {
77     int s, Case = 0;
78     init();
79     while(~scanf("%d",&s), s) {
80         printf("Case %d: ",++Case);
81         if(s == 1) {
82             puts("1");
83             continue;
84         }
85         if(s == 2) {
86             puts("-1");
87             continue;
88         }
89         ans = -1;
90         int id = find(fac, 0, fac.size() - 1, s);
91         if(fac[id].sum > s)   --id;
92         memset(sign, 0, sizeof(sign));
93         dfs(s, id, 1);
94         printf("%d
",ans);
95     }
96     return 0;
97 }

View Code