uva 11728 Alternate Task

　　vjudge 上题目链接：uva 11728

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

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int ans[];

 inline void init(int n = ) {

     for(int i = ; i <= n; ++i) {

         int sum = ;

         for(int j = ; j <= i; ++j)

             if(i % j == )   sum += j;

         if(sum <= )   ans[sum] = i;

     }

 }

 int main() {

     int s,Case = ;

     init();

     while(~scanf("%d",&s),s)

         printf("Case %d: %d\n",++Case, !ans[s]? -: ans[s]);

     return ;

 }

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

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<algorithm>

 using namespace std;

 bool vis[];

 int pri[];

 inline int init_pri(int n = ) {

     int c = ;

     for(int i = ; i <= n; ++i)

         if(!vis[i]) {

             pri[++c] = i;

             for(int j = i << ; j <= n; j += i)    vis[j] = ;

         }

     return c;

 }

 struct node {

     int sum, p, r, pow;

     node() {}

     node(int sum, int p, int r, int pow): sum(sum), p(p), r(r), pow(pow) {}

     bool operator < (const node & n2) const {

         if(sum == n2.sum)   return p < n2.p;

         return sum < n2.sum;

     }

     void print() const {

         printf("sum = %d  p = %d  r = %d  pow = %d\n",sum,p,r,pow);

     }

 };

 vector<node> fac;

 inline void init() {

     init_pri();

     for(int i = ; pri[i] <= ; ++i) {

         int sum = , mul = , len = ;

         while(sum <= ) {

             mul *= pri[i];

             sum += mul;

             if(sum > )  break;

             fac.push_back(node(sum, pri[i], ++len, mul));

         }

     }

     sort(fac.begin(), fac.end());

 }

 int find(const vector<node> &c, int low, int up, int x) {

     int mid;

     while(low <= up) {

         mid = low + up >> ;

         if(c[mid].sum == x)   return mid;

         else if(x < c[mid].sum)    up = mid - ;

         else    low = mid + ;

     }

     return low;

 }

 int ans;

 bool sign[];

 void dfs(int s, int id, int n) {

     if(s == ) {

         if(n > ans)  ans = n;

         return ;

     }

     if(s <=  || id < )   return ;

     if(!sign[fac[id].p] && s % fac[id].sum == ) {

         sign[fac[id].p] = ;

         dfs(s / fac[id].sum, id - , n * fac[id].pow);

         sign[fac[id].p] = ;

     }

     dfs(s, id - , n);

 }

 int main() {

     int s, Case = ;

     init();

     while(~scanf("%d",&s), s) {

         printf("Case %d: ",++Case);

         if(s == ) {

             puts("");

             continue;

         }

         if(s == ) {

             puts("-1");

             continue;

         }

         ans = -;

         int id = find(fac, , fac.size() - , s);

         if(fac[id].sum > s)   --id;

         memset(sign, , sizeof(sign));

         dfs(s, id, );

         printf("%d\n",ans);

     }

     return ;

 }