c++ - Sample testcase for Interviewstreet: Equations

Question

So there is a website named interviewstreet.com. Here we can find challenging programming problems. Unfortunately you have to be logged in to see the questions.

Here's a brief description of the problem I'm attempting to solve:

Find the no of positive integral solutions for the equations (1/x) + (1/y) = 1/N! (read 1 by n factorial) Print a single integer which is the no of positive integral solutions modulo 1000007.

For example, when N=3, (x,y) can be: (7,42), (9,18), (8,24), (12,12), (42,7), (18,9), (24,8). Or so I thought.

Help me please, especially you who have solved this problem. I have just coded for the problem Equations. There is something wrong with my algorithm, can I ask for output for the first 10 integers? i.e. N=2, N=3, N=4 ... N=10 so that I can find out the flaw in my algorithm. Thanks :)

EDIT: Oh, please don't post solution code as it will ruin the fun for me and for people trying to solve this :)

Answer 1

My solutions was accepted by interview street. Firstly, my solutions wasn't accepted, but after saw @Reinardus Surya Pradhit post, i realized, if pair (x, y) will be count twice, so i change it a litter bit and got success I will not post my solution here, but i can tell you the test case for all variable from N = 3 -> N = 10 Here the result

N=3: 9
N=4: 21
N=5: 63 
N=6: 135
N=7: 405
N=8: 675
N=9: 1215
N=10: 2295

My hint is: try to express N! in primes from like p1^q1 * p2^q2 * ... * pn^qn