10914 - Abundance and Perfect Numbers

[Darko]

I did *almost* the same thing, but I generated sums at the same time I generated almost odd primes (AOPs). Every sum depends on AOP and the previous sum.

I am not sure why you are sorting numbers, mine are sorted when I'm done with the generating part. I basically went through all even numbers, counted the number of shifts needed to get an odd number out of them and checked if the remaining odd number is prime.

That resulted in <1sec.. in Java!

Darko

[Sedefcho]

Darko, I just managed to get ACC in Java but my
program runs on the Judge for about 5.500 secs.

I don't see anyone with an ACC solution in Java
faster than mine It's probably because you
also have a C++ solution which is faster so the
Judge ranks you using that solution.

Do you mean 1 sec in Java on the Judge machine ?
Or do you mean 1 sec in Java on some other machine ?
If you have < 1 sec on the Judge I am quite curious how
you achieved that. It should be some quite good and
quite optimized Java code.

This one ( 10914 ) is a really nice problem.

[Darko]

Yes, 1 sec on UVa:
http://acm.uva.es/problemset/statusjudge.php?u=19882

Java is not important there, I think the rest of it is. I recoded it in C and it ran in 0.8 secs. I will send you the code in PM.

[rio]

I got AC in about 2 seconds, but in the ranklist I saw quite a few ppl solving it in less than 1 sec. Can anyone give me a hint on the better solutions? I am unable to find a trick myself

My approach to the problem is as follows:

1. Generate all primes upto 5000000
2. Getting the almost prime numbers. (Each almost prime no is of the form 2^n * primeNumber)
3. Sort the numbers
4. Run a loop through the array to precalculate the abundance value.
5. Binary search to get abun(n) for any given n

I will be very happy if anyone gives me a hint about his/her better solution. Thanks in advance.

I tried time attack, and got 0.287 sec.
In my approach, I didn't precalculate the abundance value and calculate theabundance value for each input.
Precalculating the hole abundance value takes too much time.

[Sedefcho]

I precalculate the abundance values

OK, thank you all for the replies.

[Grazyna]

I follow the strategy that it was written above.

1.calculate all primes till 5000000 and at the same time filling a sieve with almost odd numbers,
2 when reading from the input n, calculating the sum till n

I received about 10-20 times TLE.
I have no idea how to make it faster.
Thanks in advance for any suggestions.

here is the code of my precalculations:

Code: Select all

bool abud[10000100] = {0} ;
long maxn=10000100 , prime[350000] ;
long long sum ;
bool primeQ ;    
long np , n , k , i , m ;

m=6 ; while(m<maxn) { abud[m]=1 ; m=2*m ; }
prime[0]=3 ; np=1 ;
for(n=5 ; 2*n<maxn ; n+=2) {  
    primeQ=true ;
    for(i=0 ; prime[i]*prime[i]<=n ; i++)
         if (n%prime[i]==0) { primeQ=false ; break ; }
    if (primeQ) { 
         prime[np++]=n ; 
         m=2*n ; while(m<maxn) { abud[m]=1 ; m=2*m ; } } }