## 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

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

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

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

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

Thanks Angeh, now I could solve it.

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

### Re: 11889 - Benefit

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

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
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

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

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

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

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

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

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

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

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