【数论，水题】UVa 11728

题意：给出一个数S，求一个最大的数，使这个数所有的因子之和为S;

这个所谓“因子之和”不知道有没有误导性，因为一开始以为得是素数才行。后来复习了下小学数学，比如12的因子分别是1,2,3,4,6,12...

我竟无言以对T^T...

感觉复杂度应该能继续优化的。。没想到好的。。

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 using namespace std;

 const int maxn = ;

 int vis[maxn], prime[maxn], cnt;

 void pre()

 {

     int m = sqrt(maxn+0.5);

     vis[] = ;

     vis[] = ;

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

         if(!vis[i])

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

                 vis[j] = ;

     cnt = ;

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

         if(!vis[i])

             prime[cnt++] = i;

 }

 int main()

 {

     pre();

     int S, kase = ;

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

     {

         if(S == ) {printf("Case %d: 1\n", ++kase); continue;}

         bool exist = false;

         int i;

         for(i = S-; i >= ; i--)

         {

 //            if(!vis[i])

 //            {

                 //cout << i << endl;

                 int sum = ; bool ok = true;

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

                 {

                     int tmp = i/j;

                     //cout << tmp << endl;

                     if(sum > S) {ok = false; break;}

                     if(tmp*j != i) continue;

                     if(tmp != j) sum += j;

                     sum += tmp;

                 }

                 if(sum == S) {exist = true; break;}

 //            }

         }

         if(exist) printf("Case %d: %d\n", ++kase, i);

         else printf("Case %d: -1\n", ++kase);

     }

     return ;

 }

巴特西

【数论，水题】UVa 11728 - Alternate Task

最新文章

热门文章