10837  A Research Problem
Moderator: Board moderators
Aaa, domino !
If my ideas have motivated you to start solving
this problem then .... You owe me some hints
I am kidding of course.
Well, do you also use recursion ?
I can not even fix my program for inputs like 20 and 2000,
not to talk about that huge number you've given me.
If my ideas have motivated you to start solving
this problem then .... You owe me some hints
I am kidding of course.
Well, do you also use recursion ?
I can not even fix my program for inputs like 20 and 2000,
not to talk about that huge number you've given me.
Last edited by Sedefcho on Wed May 25, 2005 11:56 am, edited 3 times in total.
Code: Select all
Domino Wrote:
Is there any solution for this input
16842752
0
My program works for all test cases posted here, but i still receive Wrong Answer. I believe the above is in the judge's input, but my program says there is no solution for it. Any help would be great!
Domino, what is so special about that number?
Seems now I am in the situation you were in when you
made this post. I cover all test cases posted here
except for this number.
Well, it seems you figured it out that tests like 20 and 2000 weren't working because you didn't treat the case when the phi_n = p^k*(p1) (p prime) and the minimal n could have been p^(k+1) (it's not always p^(k+1) as you realised that for 32 it was 51).
So, my test case is like this:
N = 33817088
phi(N) = phi(2^9 * 257^2) = phi(2^9) * phi(257^2) = 2^8 * 257*256 =
= 16842752
When you work backwards from this you do the following:
16842752 = 2^8 * 257*256
min_N_from_PHI_N(257*256) = 257^2 but
min_N_from_PHI_N(2^8) = 257 (not 2^9 = 512)
so, because gcd(257^2, 257) != 1 you do not get the proper result
what should you do? well, i just tried another value for X in phi(X) = 2^8 (i try 257 and see it doesn't work and i try 512 afterwards)
If you need more hints, asks, i owe you!
So, my test case is like this:
N = 33817088
phi(N) = phi(2^9 * 257^2) = phi(2^9) * phi(257^2) = 2^8 * 257*256 =
= 16842752
When you work backwards from this you do the following:
16842752 = 2^8 * 257*256
min_N_from_PHI_N(257*256) = 257^2 but
min_N_from_PHI_N(2^8) = 257 (not 2^9 = 512)
so, because gcd(257^2, 257) != 1 you do not get the proper result
what should you do? well, i just tried another value for X in phi(X) = 2^8 (i try 257 and see it doesn't work and i try 512 afterwards)
If you need more hints, asks, i owe you!
Domino,
First, thank you for the support.
Although the algorithm is apparently not so good
in terms of performance.
Second,
The answer is : yes, I realised that.
Third,
16842752 = 2^8 * 257*256
is the answer to my question
"what is so special about this number ? "
Of course your explanations which follow
make it even more clear.
I will try to fully understand them and implement them
somehow
As far as I understand :
let's say you do this
res1 = calc_N_from_PHI_N(J) ;
res2 = calc_N_from_PHI_N(num/J);
1) If res1 and res2 have no common divisor than
we have no problem. In this case we
generate res1*res2 and we put it in the list of
our candidates for N ( whose phi(N)==num ) .
2) If they have common divisor  than what ?!
I think in that case you assume that J has the form
(p^k) * (p1) and you do this : assign p^(k+1) to res1
( res1 = p^(k+1) )
So ...
I. You actually generate a second candidate for res1
after the first one has failed due to the reason it has
a common divisor with res2 ?! Right ?
And then you put res2 * res1 in the list of your candidates.
( and that is the difference with what I do not  I would simply
reject it as gcd(res1, res2) != 1 )
Is that what you meant ?!
Or ...
II. maybe you check all numbers between
res1 and p^(k+1) in the case when res1 and res2 have
common divisor > 1 ?! I mean you calculate their PHI and you
check if it is equal to J ?!
This option No.II sounds less probable to me.
As you can see I'm slightly stupid so I need some more
explanations
By the way I am not sure "our algorithm" is always correct.
I mean mathematically. It's a sort of a heuristic algorithm.
This explains the fact I have WA. Maybe the judge should
give ACC for programs which generate correct answers
for 90% of the test cases
First, thank you for the support.
Although the algorithm is apparently not so good
in terms of performance.
Second,
Code: Select all
Well, it seems you figured it out that tests like 20 and 2000 weren't working because you didn't treat the case when the phi_n = p^k*(p1) (p prime) and the minimal n could have been p^(k+1) (it's not always p^(k+1) as you realised that for 32 it was 51).
Third,
16842752 = 2^8 * 257*256
is the answer to my question
"what is so special about this number ? "
Of course your explanations which follow
make it even more clear.
I will try to fully understand them and implement them
somehow
As far as I understand :
let's say you do this
res1 = calc_N_from_PHI_N(J) ;
res2 = calc_N_from_PHI_N(num/J);
1) If res1 and res2 have no common divisor than
we have no problem. In this case we
generate res1*res2 and we put it in the list of
our candidates for N ( whose phi(N)==num ) .
2) If they have common divisor  than what ?!
I think in that case you assume that J has the form
(p^k) * (p1) and you do this : assign p^(k+1) to res1
( res1 = p^(k+1) )
So ...
I. You actually generate a second candidate for res1
after the first one has failed due to the reason it has
a common divisor with res2 ?! Right ?
And then you put res2 * res1 in the list of your candidates.
( and that is the difference with what I do not  I would simply
reject it as gcd(res1, res2) != 1 )
Is that what you meant ?!
Or ...
II. maybe you check all numbers between
res1 and p^(k+1) in the case when res1 and res2 have
common divisor > 1 ?! I mean you calculate their PHI and you
check if it is equal to J ?!
This option No.II sounds less probable to me.
As you can see I'm slightly stupid so I need some more
explanations
By the way I am not sure "our algorithm" is always correct.
I mean mathematically. It's a sort of a heuristic algorithm.
This explains the fact I have WA. Maybe the judge should
give ACC for programs which generate correct answers
for 90% of the test cases
Hi,
Don't have much time to write much on this topic, as I'm busy with my final exam...
So you should see that your program should care more about prime numbers, rather than relatively prime numbers. The reason why the splitting 10 * 1000 doesn't work is that, your old code would certainly try splitting 1000 into 10 * 100, and thus gives 11 * 11 * 101 as an output, which is incorrect.
I think you know how to deal with cases like 20 (= 4 * 5 = 5 * (51))... The explanation given by domino is very nice~
Don't have much time to write much on this topic, as I'm busy with my final exam...
So you should see that your program should care more about prime numbers, rather than relatively prime numbers. The reason why the splitting 10 * 1000 doesn't work is that, your old code would certainly try splitting 1000 into 10 * 100, and thus gives 11 * 11 * 101 as an output, which is incorrect.
I think you know how to deal with cases like 20 (= 4 * 5 = 5 * (51))... The explanation given by domino is very nice~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Yes, this is actually what i meant..a second candidate for res1... note that sometimes N/j might fail and you might need a second candidate for res2.. it worked to get ACC although i have no proofSedefcho wrote: As far as I understand :
let's say you do this
res1 = calc_N_from_PHI_N(J) ;
res2 = calc_N_from_PHI_N(num/J);
1) If res1 and res2 have no common divisor than
we have no problem. In this case we
generate res1*res2 and we put it in the list of
our candidates for N ( whose phi(N)==num ) .
2) If they have common divisor  than what ?!
I think in that case you assume that J has the form
(p^k) * (p1) and you do this : assign p^(k+1) to res1
( res1 = p^(k+1) )
So ...
I. You actually generate a second candidate for res1
after the first one has failed due to the reason it has
a common divisor with res2 ?! Right ?
And then you put res2 * res1 in the list of your candidates.
( and that is the difference with what I do not  I would simply
reject it as gcd(res1, res2) != 1 )
Is that what you meant ?!
Yes, Domino,
With that "fix" or "patch" ( how should we call it ? )
of our algorithm I also managed to get ACC.
I doubt we can prove this algorithm is always correct
because I doubt it is always correct
Thanks for the help once again.
My runtine though is about 5 secs. Apparently it's not the
best algorithm with respect to performance.
With that "fix" or "patch" ( how should we call it ? )
of our algorithm I also managed to get ACC.
I doubt we can prove this algorithm is always correct
because I doubt it is always correct
Thanks for the help once again.
My runtine though is about 5 secs. Apparently it's not the
best algorithm with respect to performance.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Actually, a fix for your problem with 16842752 is, when you split up, you give as parameter the index of the smallest prime factor that is allowed (only prime factors > than the ones used so far are allowed).
And btw, I use a "brute force" search for N, but just memoize intermediate results, where a state has the from: phi_n, smallest allowed prime.
And btw, I use a "brute force" search for N, but just memoize intermediate results, where a state has the from: phi_n, smallest allowed prime.