UVA 11728 Alternate Task Solution

F	Alternate Task Input: Standard Input Output: Standard Output

Little Hasan loves to play number games with his friends. One day they were playing a game where one of them will speak out a positive number and the others have to tell the sum of its factors. The first one to say it correctly wins. After a while they got bored and wanted to try out a different game. Hassan then suggested about trying the reverse. That is, given a positive number S, they have to find a number whose factors add up to S. Realizing that this task is tougher than the original task, Hasan came to you for help.  Luckily Hasan owns a portable programmable device and you have decided to burn a program to this device. Given the value of S as input to the program, it will output a number whose sum of factors equal to S.

Input

Each  case of input will consist of a positive integer S<=1000. The last case is followed by a value of 0.

Output

For each case of input, there will be one line of output. It will be a positive integer whose sum of factors is equal to S. If there is more than one such integer, output the largest. If no such number exists, output -1. Adhere to the format shown in sample output.

Sample Input                             Output for Sample Input

1 102 1000 0

Case 1: 1 Case 2: 101 Case 3: -1

---

Solution

#include <stdio.h>

typedef struct{
 int s,k;
}data; 

int ans[1005];
int main(){
 int i,j,k,l,tmp,n,cas = 1;

 data a[1001];

 a[1].k = 1;
 a[1].s = 1;
 for( i = 2,j = 3; i <= 1000; i++,j++)
  a[i].k = i,a[i].s = j;
 for( i = 2; i <= 31; i++){
  for( j = i*i; j < 1001; j += i){
   a[j].s += i;
   tmp = j/i;
   if( tmp != i)
    a[j].s += tmp;
  }
 }
 

 for( i = 1000; i >= 1; i--){
  if( a[i].s <= 1000 && ans[a[i].s] == 0)
   ans[a[i].s] = a[i].k;
 }

 while( scanf("%d",&n) && n){
  if( ans[n] )
   printf("Case %d: %d\n",cas++,ans[n]);
  else 
   printf("Case %d: -1\n",cas++);
 }

 return 0;
}