11889 - Benefit

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

Moderator: Board moderators

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

11889 - Benefit

Post by patsp » Mon Nov 01, 2010 6:17 pm

I'm not able to come up with a solution...
Obviously, the brute force approach is too slow. My next step was that I tried to come up with a mathematical solution, but without success.

Can anyone help?

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11889 - Benefit

Post by Angeh » Mon Nov 01, 2010 6:27 pm

factorize the numbers
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

durjay
New poster
Posts: 13
Joined: Tue Oct 06, 2009 5:09 pm
Location: ctg

Re: 11889 - Benefit

Post by durjay » Mon Nov 01, 2010 8:04 pm

Now i solve the runtime error but i got Wa now...
Plz give me some critical input output......
Last edited by durjay on Tue Nov 02, 2010 10:53 am, edited 1 time in total.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11889 - Benefit

Post by Angeh » Mon Nov 01, 2010 8:30 pm

comment a part of your source code and submit it ... and check where in your code does lead to RTE ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

Re: 11889 - Benefit

Post by patsp » Mon Nov 01, 2010 9:08 pm

Thanks Angeh, now I could solve it.

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

Re: 11889 - Benefit

Post by patsp » Tue Nov 02, 2010 9:44 pm

Now I'm trying to optimize my solution. I currently use trial division and C++ STL map to store how many times each factor occurs.

Some tips or references on how I could optimize would be great. Thanks in advance.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11889 - Benefit

Post by Angeh » Tue Nov 02, 2010 9:57 pm

do you find all Primes and check only with primes ?
you dont ever need to save them just after finding the number of a prime in the number check it and then forget it :D
optimizing Code will not take you far ... try to optimize the Algorithm ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

Re: 11889 - Benefit

Post by patsp » Tue Nov 02, 2010 10:03 pm

I tried it with only primes. With my current algorithm for finding the value of B, I need the primes from 2 to 10^7.

How can I calculate B if I don't know the factors of A and C.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11889 - Benefit

Post by Angeh » Tue Nov 02, 2010 10:16 pm

no, you need only primes up to SQRT(10^7)...
each number has at most only one prime number Greater than sqrt(n);
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

Re: 11889 - Benefit

Post by patsp » Tue Nov 02, 2010 10:22 pm

Ah, sure, I thought C could be a prime number... but then it cannot be an lcm..

But what do you mean with check it and then forget it. For finding B, I currently use the fact that the lcm of two numbers is always the product of the prime factors which occur more often in the two numbers, so I don't know how I could solve without storing the amount of them in C and A.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11889 - Benefit

Post by Angeh » Tue Nov 02, 2010 11:08 pm

Find the number of each Prime in C ... and then check A%(Pi^ci) ...
think what can you get from the result of A%(Pi^ci) ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

ItaloSpedini
New poster
Posts: 9
Joined: Sat Sep 11, 2010 1:21 am
Location: Rio de Janeiro - Brasil

Re: 11889 - Benefit

Post by ItaloSpedini » Tue Nov 23, 2010 12:57 am

Could anyone post some inputs and their outputs? Thanks. I'm getting WA or TLE.
Computer Science - UERJ - Rio de Janeiro - Brasil.

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

Re: 11889 - Benefit

Post by patsp » Tue Nov 23, 2010 8:19 pm

Here are some testcases, hope they help.

input:

Code: Select all

23
2 6
32 1760
7 16
59 44132
218 8066
846 192042
469 28609
676 29068
5 2855
458 115874
77 4081
237 68019
697 14637
74 72298
493 340170
732 104676
355 103305
878 179990
357 111384
157 90275
973 2919
28 6188
429 27456
output:

Code: Select all

3
55
NO SOLUTION
748
37
227
61
43
571
253
53
287
21
977
690
143
291
205
936
575
3
221
64

ItaloSpedini
New poster
Posts: 9
Joined: Sat Sep 11, 2010 1:21 am
Location: Rio de Janeiro - Brasil

Re: 11889 - Benefit

Post by ItaloSpedini » Wed Nov 24, 2010 2:53 am

patsp wrote:Here are some testcases, hope they help.

input:

Code: Select all

23
2 6
32 1760
7 16
59 44132
218 8066
846 192042
469 28609
676 29068
5 2855
458 115874
77 4081
237 68019
697 14637
74 72298
493 340170
732 104676
355 103305
878 179990
357 111384
157 90275
973 2919
28 6188
429 27456
output:

Code: Select all

3
55
NO SOLUTION
748
37
227
61
43
571
253
53
287
21
977
690
143
291
205
936
575
3
221
64
Thanks, i'll try these cases.
Computer Science - UERJ - Rio de Janeiro - Brasil.

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm
Location: CUET,Chittagong,Bangladesh

Re: 11889 - Benefit

Post by naseef_07cuet » Wed Dec 01, 2010 1:13 pm

Can anyone explain me about the problem?
If you have determination, you can do anything you want....:)

Post Reply

Return to “Volume 118 (11800-11899)”