UVA 11728 - Alternate Task 数学

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
ﬁrst one to say it correctly wins. After a while they got bored and wanted to try out a diﬀerent game.
Hassan then suggested about trying the reverse. That is, given a positive number S, they have to ﬁnd
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
1
102
1000
0
Sample Output
Case 1: 1
Case 2: 101
Case 3: -1

题意：给你一个S，问你n的因子数的和为S ，求n

题解： S很小，求出 n的因子和 S，数组取反就好了

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std ;

typedef long long ll;

const int N=;

int a[N + ], b[N + ];

void init() {

    memset(a,-,sizeof(a));

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

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

        b[j] += i;

    }

    if(b[i] < N) a[b[i]] = i;

 }

}

int main() {

    init();

    int  cas = , n;

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

        if(n == ) break;

        printf("Case %d: %d\n", cas++, a[n]);

    }

    return ;

}

代码

巴特西

UVA 11728 - Alternate Task 数学

最新文章

热门文章