## 10837 - A Research Problem

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

Moderator: Board moderators

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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.
Last edited by Sedefcho on Wed May 25, 2005 11:56 am, edited 3 times in total.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Now I made a small change which produces this output:
4328653313 for input=16842752.

Which is not the correct answer.

Any hints from you, domino or from observer
will be appreciated.

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
Thanks domino. I was really stuck on this problem. Now its AC.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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.

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm
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*(p-1) (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! domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm
Oh, and by the way, how are people solving this in under 0.1s? I have 0.5s runtime after hashing the results with a STL map. Could someone share some hints? (i see Adrian Kuegel for example has a really fast solution)

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Domino,

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*(p-1) (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).
``````
The answer is : yes, I realised that.

Third,

16842752 = 2^8 * 257*256
is the answer to my question
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) * (p-1) 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 Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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 * (5-1))... 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

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm
Sedefcho 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) * (p-1) 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, 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 proof Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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.