## Friday, October 19, 2012

### InterviewStreet: Equation.

InterviewStreet:EQUATION.

## Problem:

EQUATIONS (45 points)
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.

Input:
N
Output:
Number of positive integral solutions for (x,y) modulo 1000007
Constraints:
1 <= N <= 10^6
Sample Input00:
1
Sample Output00:
1
Sample Input01:
32327
Sample Output 01:
656502
Sample Input02:
40921
Sample Output 02:
686720

## Solution:

No of solutions for the equation XY=N! is
(e1+1)(e2+1)………..(en+1)
where e1,e2…en are multiplicities of Prime Numbers below N.
For Ex: XY=4!
No of primes below 4= {2,3}
4!= 24= 23*31
where 3 and 1 are prime multiplicities of 24.
so applying the formula (3+1)*(1+1)=8 (no of factors of 24={1,2,3,4,6,8,12,24}.
Now the equation 1⁄x+1⁄y= N! can be transformed into
(x-N!)(y-N!)=N!2
Hence No. of solutions of the above equation is
(2e1+1)(2e2+1)………..(2en+1)
Hence to solve the problem:
1) First find out the primes less than N
2) Find the prime multiplicities
3) Apply the formula.

For step two, it's not easy to have a fast solution. Compare with two methods I provided here, I still don't know how the second one could work, while the first one is definitely too slow.

Updated: This LINK greatly explains why the second method is also right.

## Source Code:

```import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.List;

public class Solution {

private static final int MOD = 1000007;

private boolean[] isPrime;
private int[] multiplier;
private List<Integer> prime;

public static void main(String[] args) throws Exception {
Solution main = new Solution();
main.run();
System.exit(0);
}

public void run() throws Exception {
isPrime = new boolean[N + 1];
multiplier = new int[N + 1];
prime = new ArrayList<Integer>();
generatePrime(N);
// for (int i = 0; i <= N; i++)
// System.out.println("" + i + ", " + isPrime[i]);
generateMultiplier(N);

long sum = 1L;
for (int i = 1; i <= N; i++)
if (multiplier[i] != 0) {
sum *= (long) (2 * multiplier[i] + 1) % MOD;
sum %= MOD;
}
System.out.println(sum);
}

public void generatePrime(int N) {
for (int i = 2; i <= N; i++)
if (isPrime[i] == false) {
for (int j = 2; j * i <= N; j++)
isPrime[i * j] = true;
}
}

public void generateMultiplier(int N) {
// int left = 1;
// for (int i = 1; i <= N; i++) {
// left *= i;
// for (int j : prime) {
// while (left % j == 0) {
// multiplier[j]++;
// left /= j;
// }
// if (left < j) // It helps prune and save the time.
// break;
// }
// }
for (int j : prime) {
int cpy = N;
int e = 0;
while (cpy != 0) {
e += cpy / j;
cpy /= j;
}
multiplier[j] = e;
}
}

public boolean check(int x, int N) {

return true;
}

}
```