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
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.
(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}.
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)
(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.
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; } }