11073 - Euler's Totient Function

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

Moderator: Board moderators

Sumon
New poster
Posts: 17
Joined: Fri May 30, 2003 8:14 pm
Location: Bangladesh
Contact:

11073 - Euler's Totient Function

Post by Sumon »

I have some TLE problem with this problem :oops: . Can anyone give me some test cases,for which a great deal of computation required or a lot of output comes?? Can anyone tell how many numbers can be output at best and for which input???
Change your view,your life will be changed.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: Test Cases for 11073???

Post by Martin Macko »

Sumon wrote:I have some TLE problem with this problem :oops: . Can anyone give me some test cases,for which a great deal of computation required or a lot of output comes?? Can anyone tell how many numbers can be output at best and for which input???
Try these:

Code: Select all

2
4
5
7
8
9
10
480
5760
999999936
999999960
999999984
999999997
999999998
999999999
My AC's output:

Code: Select all

3 4 6
5 8 10 12
No solution.
No solution.
15 16 20 24 30
No solution.
11 22
527 533 715 723 861 915 964 975 976 992 1054 1066 1144 1148 1155 1220 1232 1240 1300 1400 1430 1446 1464 1476 1488 1540 1584 1716 1722 1800 1830 1848 1860 1950 1980 2100 2310
5917 5983 6347 6851 6919 7259 7469 7585 8075 8435 8979 9021 9231 9333 9399 9603 10659 10845 11067 11193 11475 11584 11685 11781 11834 11895 11966 11972 12028 12045 12136 12308 12464 12532 12688 12694 12848 12896 12915 13024 13376 13496 13664 13702 13838 13888 14212 14480 14518 14600 14756 14800 14924 14938 15015 15170 15200 15580 15860 16016 16060 16120 16150 16280 16720 16870 17080 17352 17360 17376 17568 17712 17856 17958 18042 18200 18204 18462 18666 18696 18798 18972 19008 19032 19188 19206 19272 19344 19536 20020 20064 20196 20244 20496 20592 20664 20832 21318 21600 21690 21720 21900 21960 22134 22140 22176 22200 22320 22386 22800 22950 23370 23400 23562 23760 23790 24024 24090 24180 24420 25080 25200 25620 25740 25830 26040 27300 27720 30030
999999937 1001069249 1002008467 1006024199 1009300739 1020306869 1025379499 1055555507 1075855639 1097223179 1121528029 1174146323 1196327713 1263889991 1267361395 1273718185 1499999931 1509036549 1509616701 1518788013 1528847487 1531995369 1538135631 1579861465 1593750357 1625001417 1634873721 1772437443 1927083765 1999999874 2002138498 2004016934 2012048398 2012048732 2018601478 2025050684 2027778232 2031250455 2037949096 2040613738 2042660492 2050758998 2055556016 2111111014 2111111584 2151711278 2179831628 2194446358 2243056058 2348292646 2363249924 2392655426 2527778344 2527779982 2534722790 2547436370 2569445020 2638889480 2999999862 3000000672 3018073098 3019233402 3037576026 3038464188 3041667348 3056923644 3057694974 3063990738 3076271262 3083334024 3159722930 3166667376 3187500714 3250000728 3250002834 3269747442 3500000784 3544874886 3750000840 3791667516 3854167530 3958334220 4062500910 4375000980
1249999955 1999999928 2499999910 2999999892
1002688529 1083333329 1499999979 1749999993 1999999972 2005377058 2166666658 2333333324 2999999958 2999999988 3499999986
No solution.
No solution.
No solution.
I think that one of the longlest outputs is for number 583925760.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen »

Can someone tell me what the biggest number is in the output?

Is it smaller than 10000000000?

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

Wei-Ming Chen wrote:Can someone tell me what the biggest number is in the output?

Is it smaller than 10000000000?
Hard to say. I know only that they fit to long long int.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen »

I got 19639 outputs for the input 583925760

Can someone tell me is it right?

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ »

map<int, int> and generate seems too slow? I found that in the ranklist some people got time < 1s :-? Some hints please?

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Wei-Ming Chen wrote:I got 19639 outputs for the input 583925760

Can someone tell me is it right?
Same here.

FAQ - I don't know your algorithm, but map is rather slow. All I use here are 3 arrays (2 for caching primes, 1 for final result) and a recursive function with nice property of generating only correct answers and each exactly once.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

Sumon
New poster
Posts: 17
Joined: Fri May 30, 2003 8:14 pm
Location: Bangladesh
Contact:

Thanks Anyway

Post by Sumon »

I got Accepted this 11073 :lol: .I made some silly structural mistake that took useless extra time. Thanks to all anyway for giving what i really wanted and could help me if i didn't get accepted.
Change your view,your life will be changed.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

In my program I use map< pair<int, int>, vector<long long> > and it runs in 2.766 seconds, so map is not too slow, try to optimize your algorithm.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

Wei-Ming Chen wrote:I got 19639 outputs for the input 583925760

Can someone tell me is it right?
Yes, it's right.

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 »

hi,
what is the algorithm used in the problem. please post some resources and hints.
i made some observations.
if m is odd no solution
if x is a solution and it is odd then 2*x is a solution

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 »

can someone post the paper that is to be read or how should one go about solving this problem. i have tried it but am out of ideas. All i know i could find from observations is that the odd solutions lie between n+1 and 4*n (maybe wrong). But for 10^9 it is too long.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

I've used backtracking, it's nothing too complicated.
Just use the formula for phi(n), given in the problem statement backwards; first factorize x, then try to choose a subset of its prime factors to make some (prime-1)*prime^e, remove these factors and backtrack.

Sumon
New poster
Posts: 17
Joined: Fri May 30, 2003 8:14 pm
Location: Bangladesh
Contact:

Take it easy

Post by Sumon »

temper_3243 wrote:can someone post the paper that is to be read or how should one go about solving this problem. i have tried it but am out of ideas. All i know i could find from observations is that the odd solutions lie between n+1 and 4*n (maybe wrong). But for 10^9 it is too long.
I didn't considered any number theoritical special conditions and applied straightforward bactracking,then got accepted in .908sec. So,don't make things worse by adding more and more conditions. Just find divisors of n and try to construct subset of divisors d for generating the output by applying the reverse of Euler's function. :wink:
Change your view,your life will be changed.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 »

well i am getting TLE, can any one have a look at my BKTRK() ? well... in my process i had written PRIME() function which returns 0/1 according to whether it is prime or not when i need to check primality for a number > sqrt(10^9) but no one here mentioned for such process. so am i doing inefficient some where?

Code: Select all

GOT AC. Cutting the code except the heuristics for fellows:

	if(n==1)
	{
*********************
	}

	if(n&1)
*********************

	if(n < prime[pos]*(prime[pos]-1) && n+1>prime[pos])
	{
*********************
	}

	if(n < prime[pos]-1)
*********************

	if(pos==sz && n+1>prime[pos])
	{
*********************
	}

Last edited by shanto86 on Sat Aug 19, 2006 8:52 pm, edited 1 time in total.
Self judging is the best judging!

Post Reply

Return to “Volume 110 (11000-11099)”