1180 - Perfect Numbers

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

Moderator: Board moderators

Post Reply
User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

1180 - Perfect Numbers

Post by uDebug » Thu Apr 03, 2014 3:00 pm

On this problem, note that the integers on the second line are separated by commas - and not spaces.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 1180 - Perfect Numbers

Post by Shahidul.CSE » Sat Aug 02, 2014 12:24 pm

Code: Select all

cut
Last edited by Shahidul.CSE on Mon Dec 08, 2014 6:18 pm, edited 2 times in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

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

Re: 1180 - Perfect Numbers

Post by lighted » Sat Aug 02, 2014 3:24 pm

Why do you think that p is one digit number? It can be greater than 9.

Code: Select all

p=num[i]-'0';
n=pow(2,p-1)*(pow(2,p)-1);
This problem is tricky. I checked that p can be greater than 1000.
So you can forget about checking if sum of proper divisors are equal to a number.
And you don't need to check it.

Think about this condition
Euclid proved that an even number is perfect if it has the form
2^(p-1) * (2^p - 1)
where both p and 2^p - 1 are prime numbers.
And this condition
The largest perfect number in this problem will not exceed 2^33
By the way i read p this way

Code: Select all

scanf("%d", &t);

while (t--) {

  scanf("%d", &p);

  if (t) scanf(" %c", &c);

  ..
}
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 1180 - Perfect Numbers

Post by Shahidul.CSE » Sat Aug 02, 2014 5:32 pm

Code: Select all

cut
Last edited by Shahidul.CSE on Mon Dec 08, 2014 6:17 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

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

Re: 1180 - Perfect Numbers

Post by lighted » Sat Aug 02, 2014 10:11 pm

If max value of perfect number is 2^33.

Then 2^(p-1) * (2^p - 1) <= 2^33. Can you get max value for p? :)

If given p is greater than max value i print "No" because they will be not perfect numbers according to problem description. :)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 1180 - Perfect Numbers

Post by Shahidul.CSE » Sun Aug 03, 2014 5:11 am

Code: Select all

cut
Last edited by Shahidul.CSE on Mon Dec 08, 2014 6:17 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

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

Re: 1180 - Perfect Numbers

Post by lighted » Sun Aug 03, 2014 4:21 pm

Your prime checking is wrong.
When you solve problems relating to prime numbers -> Add a condition that 1 is not a prime. :)
(if problem description didn't said anything about it)

It would be better if you make function isPrime(int n) that checks if number is prime. :)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Helaluddin_brur
New poster
Posts: 15
Joined: Tue Oct 21, 2014 4:08 pm
Location: Bangladesh
Contact:

Re: 1180 - Perfect Numbers

Post by Helaluddin_brur » Fri Nov 28, 2014 9:03 pm

getting TL

any suggestion ?

here is my code

Code: Select all

#include<stdio.h>
#include<math.h>
int main()
{
    unsigned long long int n,i,j,p,sum,t;
    //freopen("1180.txt","r",stdin);
    while(scanf("%llu",&t)==1)
    {
        for(i=0;i<t;i++)
        {
            scanf("%llu",&p);
            if(i<t-1)
                scanf(",");
            sum=0,n=0;
            n=pow((double)2,p-1)*(pow((double)2,p)-1);
            for(j=1;j<n;j++)
            {
                if(n%j==0)
                    sum+=j;
            }
            if(n==sum)
                printf("Yes\n");
            else
                printf("No\n");
        }

    }
    return 0;

}
Last edited by Helaluddin_brur on Thu Aug 13, 2015 7:57 pm, edited 3 times in total.

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 1180 - Perfect Numbers

Post by Shahidul.CSE » Fri Nov 28, 2014 9:20 pm

Helaluddin_brur,
According to your code, you should print Yes, when both f and f1 is 0.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

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

Re: 1180 - Perfect Numbers

Post by lighted » Sat Nov 29, 2014 1:04 pm

Doesn't match sample I/O. Input numbers are separated by commas(','). You should read this commas from standart input.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

ssavi
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

Re: 1180 - Perfect Numbers

Post by ssavi » Thu Dec 04, 2014 10:04 pm

Why I am getting TLE ?? Please Help ....

Code: Select all

#include<stdio.h>
#include<math.h>
int main()
{
    long long int n, i, p, a[100000], j, d, sum;
    char ch;
    while(scanf("%lld",&n)==1)
    {
        for(i=1;i<=n;i++)
            {
               scanf("%lld,",&a[i]);
               scanf("%c",&ch);
            }
       for(i=1;i<=n;i++)
       {
           d = (pow(2,a[i]-1))*(pow(2,a[i])-1);
           sum=0;
           for(j=1;j<d;j++)
           {
               if((d%j)==0)
                  sum = sum+j;
           }
           if(sum==d)
            printf("Yes\n");
           else
            printf("No\n");
       }
    }
    return 0;
}
I know I am a Failure Guy . :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1180 - Perfect Numbers

Post by brianfry713 » Fri Dec 05, 2014 12:37 am

Check input and AC output for thousands of problems on uDebug!

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

Re: 1180 - Perfect Numbers

Post by lighted » Fri Dec 05, 2014 11:44 am

ssavi, if you want to optimize your code read posts in this thread.
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 11 (1100-1199)”