Box and Ball System
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 Ai.
When the safe is opened the number of divisors of i equals to the number of divisors of Ai 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*105+9).
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.
For each test case, print the number of combinations modulo 500009 (5*105+9).
1 ≤ T ≤ 100000 (105)
3 ≤ N ≤ 2000000000 (2*109)
3 3 5 100
1 5 43264
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
|Tags||feb12, laycurse, medium|
|Time Limit:||0.222936 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.