Box and Ball System

Problem code: BBSYSTEM

All Submissions

All submissions for this problem are available.

Chef Ciel has forgotten the combination to the safe. It's a serious incident, because the safe contains this month's waitstaff salaries.

To open the safe, N boxes and N balls are used. The safe has N boxes that numbered from 1 to N uniquely. Each box can contain only one ball. Now, the box i contains one ball that numbered i, and the safe is locked.

The only things which Ciel remember for unlocking the safe are the followings:

She must put every ball into some box.
Let the box i contains the ball A_i. When the safe is opened the number of divisors of i equals to the number of divisors of A_i for all i from 1 to N.

How many combinations which satisfy above conditions should she check? The number of combinations can be very large, so you should print this number modulo 500009 (5*10⁵+9).

Input

The first line contains an integer T, the number of test cases. Then T test cases follow. The only line of each test case contains an integer N.

Output

For each test case, print the number of combinations modulo 500009 (5*10⁵+9).

Constraints

1 ≤ T ≤ 100000 (10⁵)
3 ≤ N ≤ 2000000000 (2*10⁹)

Sample Input

Sample Output

1
5
43264

Output details

In the first case, the valid combination is

Box: 123
Ball: 132

since the number of divisors of 2 is equal to the number of divisors of 3.

In the second case, the valid combinations are

Box: 12345 12345 12345 12345 12345
Ball: 12543 13245 13542 15243 15342

Author:	laycurse
Date Added:	29-08-2011
Time Limit:	3 sec
Source Limit:	50000 Bytes
Languages:	ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC

Submit

Comments

Login or Register to post a comment.

y is 123 not counted in first

calc_saransh @ 1 Feb 2012 08:06 PM

y is 123 not counted in first case? i am not clear on the question?

@calc_saransh Please read the

hiroto_adm @ 1 Feb 2012 08:16 PM

@calc_saransh Please read the problem statement carefully.

The time limit of 3s is total

cabraconstante @ 1 Feb 2012 09:55 PM

The time limit of 3s is total time allowed for the successful completion of ALL the test cases i.e. if the user enters T=100000 then the total time taken should be 3s ONLY - right?

@cabraconstante This is the

hiroto_adm @ 2 Feb 2012 01:59 AM

@cabraconstante This is the time limit per file. The judge test files are the same format as the sample input (including T, and T test cases). Your code must run in 3 seconds for each test file.

@cabraconstante You can also

hiroto_adm @ 2 Feb 2012 02:05 AM

@cabraconstante You can also see http://www.codechef.com/wiki/faq#How_does_the_time_limit_work

why isn't 123 counted in the

lazzrov @ 2 Feb 2012 02:52 AM

why isn't 123 counted in the first case?

@lazzrov Please read the

hiroto_adm @ 2 Feb 2012 03:07 AM

@lazzrov Please read the problem statement carefully.

how many test files in this

jehad @ 2 Feb 2012 10:46 AM

how many test files in this problem ?

@lazzrov - i understand it as

chaitu2289 @ 2 Feb 2012 12:08 PM

@lazzrov - i understand it as "presently the sequence of boxes 1,2,3 contains balls numbered 1,2,3 and the safe is locked and now we have to find other sequences that satisfies the conditions in the problem statement" . Please correct me if i am wrong

@Admin: Can you double check

shadow @ 2 Feb 2012 12:44 PM

@Admin: Can you double check the time limit. I am 200% sure my program is running within time limits, but I am getting TLE on judge. Thanks in advance.

@lazzrov Sorry, it should be

hiroto_adm @ 2 Feb 2012 01:37 PM

@lazzrov Sorry, it should be "Now, the box i contains one ball numbered i, and the safe is locked." or "Now, the box i contains one ball that is numbered i, and the safe is locked." You can see chaitu2289's comment.

@jehad The number of test

hiroto_adm @ 2 Feb 2012 01:39 PM

@jehad The number of test files is not published. Why do you know it?

@shadow I think the time

hiroto_adm @ 2 Feb 2012 01:44 PM

@shadow I think the time limit is not tight at all. Please remember that CodeChef's server may about 5~10 times slower than your computer if your computer is not so old.

@hiroto_adm- Thanks.

cabraconstante @ 2 Feb 2012 04:22 PM

@hiroto_adm- Thanks.

@hiroto_adm - I am not able

cabraconstante @ 2 Feb 2012 07:54 PM

@hiroto_adm - I am not able to validate my answers. On my system I am getting correct answers for the sample inputs. However, my answers are coming incorrect while running on the code chef server. Can you pls provide two - three more sample inputs preferably > 100 so that I can validate it.

@cabraconstante Please don't

hiroto_adm @ 2 Feb 2012 10:20 PM

@cabraconstante Please don't require additional test cases.

hiroto_adm @ are u

armuk_winhsa @ 2 Feb 2012 11:53 PM

hiroto_adm @ are u considering only prime divisors??

@armuk_winhsa No. For

hiroto_adm @ 3 Feb 2012 07:26 AM

@armuk_winhsa No. For example, 4 has three divisors (1, 2, 4).

@admin giving constraints

phaniram @ 3 Feb 2012 01:58 PM

@admin giving constraints such as 3 ≤ N ≤ 2000000000 (2*10^9) requires to allocate more memory how can i increase heap size?

@phaniram I think that the

hiroto_adm @ 3 Feb 2012 03:20 PM

@phaniram I think that the memory limit may be around 200 MB. You cannot use much memory such as int array[2000000000].

@pdwd It seems to me that

hiroto_adm @ 3 Feb 2012 03:28 PM

@pdwd It seems to me that your understanding about the time limit is correct. I don't know, but the CodeChef's server is just slower than your computer, or your example was not the worst one, or your code has bugs, or....

how can i find the deadline

dineshj92 @ 3 Feb 2012 07:31 PM

how can i find the deadline for submitting answer

@dineshj92 This contest runs

hiroto_adm @ 3 Feb 2012 09:09 PM

@dineshj92 This contest runs until 11th Feb. 15:00 (IST). The remaining time is written in the top page of the contest ( http://www.codechef.com/FEB12 )

@admin:I am getting TLE but i

amriteshanand @ 4 Feb 2012 02:02 PM

@admin:I am getting TLE but i think my solution is optimum.Can u please see into my code and confirm that a more optimum solution exists.Please..

"Now, the box i contains one

sankalp91 @ 4 Feb 2012 03:49 PM

"Now, the box i contains one ball that numbered i, and the safe is locked." -- What does this statement mean?

@amriteshanand I cannot give

hiroto_adm @ 4 Feb 2012 06:18 PM

@amriteshanand I cannot give advice to you. If I do, it is unfair. So, I cannot tell you whether your solution is optimal or not.

@sankalp91 Please see the

hiroto_adm @ 4 Feb 2012 06:21 PM

@sankalp91 Please see the comments "chaitu2289 @ 2 Feb 2012 12:08 PM" and "hiroto_adm @ 2 Feb 2012 01:37 PM". If you still cannot understand the statement after that, please ask it once more.

What are specifications of

sankalp91 @ 5 Feb 2012 03:26 PM

What are specifications of the codechef judge?

@sankalp91 http://www.codeche

hiroto_adm @ 5 Feb 2012 05:32 PM

@sankalp91 http://www.codechef.com/wiki/environment-details http://www.codechef.com/wiki/faq#Why_is_my_code_not_correct

i am getting Time Limit Error

sanjivgorka @ 6 Feb 2012 03:44 PM

i am getting Time Limit Error for my Python 3 code .. hmmm any advises :)

@sanjivgorka Please don't

hiroto_adm @ 6 Feb 2012 07:19 PM

@sanjivgorka Please don't require any hint during the contest. The information about the time limit is in the FAQ. For example: http://www.codechef.com/wiki/faq#How_does_the_time_limit_work http://www.codechef.com/wiki/faq#Why_do_I_get_a_Time_Limit_Exceeded

how to increase the array

amitsingh1991 @ 7 Feb 2012 12:05 AM

how to increase the array size??

@admin: I have doubt like

little_chuck @ 7 Feb 2012 09:02 AM

@admin: I have doubt like only numbers of combinations possible is to printed as output right?

Can I read all test in input

darkdiver @ 8 Feb 2012 07:06 PM

Can I read all test in input anf after it start print answer? Or i must read 1 test and write 1 answer, read 1, write one.

modulo 500009 means remainder

architmittal @ 8 Feb 2012 10:55 PM

modulo 500009 means remainder on dividing by 500009?????

do you accept math.h

saayaa @ 9 Feb 2012 11:06 AM

do you accept math.h library...???

@darkdiver You can.

hiroto_adm @ 9 Feb 2012 12:04 PM

@darkdiver You can.

@architmittal Yes.

hiroto_adm @ 9 Feb 2012 12:04 PM

@architmittal Yes.

@saayaa The judge use the

hiroto_adm @ 9 Feb 2012 12:08 PM

@saayaa The judge use the flag "-lm" for C and C++. So, you can use the functions in math library.

thanx.... hiroto_adm....so i

saayaa @ 9 Feb 2012 01:57 PM

thanx.... hiroto_adm....so i will be using it...

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a non-commercial competitive programming community

In order to report copyright violations of any kind, send in an email to copyright@codechef.com

CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month. We also aim to have training sessions and discussions related to algorithms, binary search, technicalities like array size and the likes. Apart from providing a platform for programming competitions, CodeChef also has various algorithm tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our programming contest judge accepts solutions in over 35+ programming languages. Preparing for coding contests were never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming challenges that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly coding contest and the shorter format Cook-off coding contest. Put yourself up for recognition and win great prizes. Our programming contests have prizes worth up to Rs.20,000 and $700lots more CodeChef goodies up for grabs.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be a part of CodeChef's Forums and interact with all our programmers - they love helping out other programmers and sharing their ideas. Have discussions around binary search, array size, branch-and-bound, Dijkstra's algorithm, Encryption algorithm and more by visiting the CodeChef Forums and Wiki section.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. You can also host a coding contest for your institute on CodeChef, organize an algorithm event and be a guest author on our blog.

Go For Gold

The Go for Gold Initiative was launched about a year after CodeChef was incepted, to help prepare Indian students for the ACM ICPC World Finals competition. In the run up to the ACM ICPC competition, the Go for Gold initiative uses CodeChef as a platform to train students for the ACM ICPC competition via multiple warm up contests. As an added incentive the Go for Gold initiative is also offering over Rs.8 lacs to the Indian team that beats the 29th position at the ACM ICPC world finals. Find out more about the Go for Gold and the ACM ICPC competition here.

Domain Name Registration, Web hosting, and Website Design provided by BigRock.com

Site Navigation