11889  Benefit
Moderator: Board moderators
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?
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?
Re: 11889  Benefit
factorize the numbers
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)
Re: 11889  Benefit
Now i solve the runtime error but i got Wa now...
Plz give me some critical input output......
Plz give me some critical input output......
Last edited by durjay on Tue Nov 02, 2010 10:53 am, edited 1 time in total.
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;)
Beliefs are not facts, believe what you need to believe;)
Re: 11889  Benefit
Thanks Angeh, now I could solve it.
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.
Some tips or references on how I could optimize would be great. Thanks in advance.
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 ...
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;)
Beliefs are not facts, believe what you need to believe;)
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.
How can I calculate B if I don't know the factors of A and C.
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);
each number has at most only one prime number Greater than sqrt(n);
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)
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.
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.
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) ...
think what can you get from the result of A%(Pi^ci) ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)

 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.
Re: 11889  Benefit
Here are some testcases, hope they help.
input:
output:
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
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

 New poster
 Posts: 9
 Joined: Sat Sep 11, 2010 1:21 am
 Location: Rio de Janeiro  Brasil
Re: 11889  Benefit
Thanks, i'll try these cases.patsp wrote:Here are some testcases, hope they help.
input:output: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
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
Computer Science  UERJ  Rio de Janeiro  Brasil.

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