InterviewStreet: Equation.

Problem Links:

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
(e₁+1)(e₂+1)………..(e_n+1)
where e₁,e₂…e_n are multiplicities of Prime Numbers below N.

For Ex: XY=4!
No of primes below 4= {2,3}
4!= 24= 2³*3¹
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!²
Hence No. of solutions of the above equation is
(2e₁+1)(2e₂+1)………..(2e_n+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.io.InputStreamReader;
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 {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  int N = Integer.parseInt(br.readLine());
  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) {
    prime.add(i);
    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;
 }

}