10791 - Minimum Sum LCM

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sajid_1989
New poster
Posts: 1
Joined: Thu Nov 11, 2010 6:56 am

Re: 10791 - Minimum Sum LCM

Post by sajid_1989 » Wed Nov 16, 2011 7:22 pm

I am getting Runtime Error. Can't find the reason. Need help badly :(

Code: Select all

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <cctype>
#include <utility>
#include <cstdlib>
#include <algorithm>
#include <bitset>

using namespace std;

#define rep(i, b) for(i = 0; i < b; i++)
#define For(i, a, b) for( i = a; i <= b; i++)
#define N 1000000
#define NN 66000
#define PI acos( -1.0 )
#define INF 2147483646
#define LL long long
#define modu 100000007


bool mark[N + 5];
vector <int> primeList;

int min(LL a, LL b)
{
	if(a < b) return a;
	return b;
}

LL power(int x, int y)
{
	LL pro = 1;
	for(int i = y; i > 0; i--)
		pro *= x;

	return pro;
}

void mySieve()
{
    int i, j;
    memset(mark, true, sizeof(mark));

    mark[0] = mark[1] = false;
    for(i = 4; i <= N; i += 2)  mark[i] = false;

    for(i = 3; i * i <= N; i += 2)
    {
        if(mark[i])
        {
            for(j = i * i; j <= N; j += i)
                mark[j] = false;
        }
    }

    primeList.push_back(2);
    for(i = 3; i < N; i += 2)
    {
        if(mark[i])    primeList.push_back(i);
    }


   // printf("%d\n", primeList.size());
	//printf("%d \n", primeList[primeList.size() - 1]);
}

int main(void)
{
    mySieve();

    LL n;
    int Case = 0;
    while(scanf("%lld", &n) && n)
    {
        int i, j;
        LL num = n;
        i = 0;
        LL sum = 0;
        while(num != 1 && primeList[i] * primeList[i] <= num)
        {
			int count = 0;
            while(num % primeList[i] == 0)
            {
                num /= primeList[i];
                count++;
            }
			if(count != 0)
				sum += power(primeList[i], count);
            i++;
        }
		if(num == n || sum == n)
			sum = n + 1;
        else if(num != 1){
            sum += num;
			sum = min(n + 1, sum);
		}

        printf("Case %d: %lld\n", ++Case, sum);
    }

    return 0;
}

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10791 - Minimum Sum LCM

Post by lighted » Wed Aug 27, 2014 9:49 pm

Input

Code: Select all

1
0
Output

Code: Select all

Case 1: 2
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 107 (10700-10799)”