11889 - Benefit

[patsp]

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]

factorize the numbers

[durjay]

Now i solve the runtime error but i got Wa now...
Plz give me some critical input output......

[Angeh]

comment a part of your source code and submit it ... and check where in your code does lead to RTE ...

[patsp]

Thanks Angeh, now I could solve it.

[patsp]

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]

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

[patsp]

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]

no, you need only primes up to SQRT(10^7)...
each number has at most only one prime number Greater than sqrt(n);

[patsp]

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]

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

[ItaloSpedini]

Could anyone post some inputs and their outputs? Thanks. I'm getting WA or TLE.

[patsp]

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]

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.

[naseef_07cuet]

Can anyone explain me about the problem?