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

题目链接

题意:给出一个数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 ;
}
上一篇:js完成密码输入为空,和两次输入不一致


下一篇:使用python操作hdfs,并grep想要的数据