- Prepare
- Mathematics
- Number Theory
- Equations
- Discussions
Equations
Equations
+ 3 comments Let's take a look here ,
(1/x) + (1/y) =(1/n!) number of solutions
let's n! as p okk ? Now ..
(1/x) + (1/y) =(1/p)
(x+y)/(xy) = (1/p)
px + py =xy - px -py +xy=0 p^2 - px -py +xy =p^2 [ adding p^2 both sides ] p(p-x) -y(p-x)=p^2 (p-y) (p-x) =p^2 Now , think (p-y) as A and (p-x) as B So , A*B = p^2 Now , if anybody asks u the number of solutions of this solution . Then It will make U common sense that the number of divisors will be unique solutins Because Look At this . Let's think p^2 =36 So solutions are (value of A and B) a * b 1*36=36 2*18=36 3*12=36 4*9=36 6*6=36 a * b 36*1=36 18*2=36 12*3=36 9*4=36 Total 9 unique solutions . Now , put n! in p So , U have to find out the number of divisors of (n!)^2 . That's all !!! Hope it helps My github link
https://github.com/joy-mollick/Problem-Solving-Solutions-Math-Greedy-
+ 0 comments #!/bin/python3 import os import sys # n = N! # x + y = xy / n # xn + yn = xy # xy - xn - yn + n^2 = n^2 # (x-n)(y-n) = n^2 # XY = n^2 # answer is number of factors of N!^2 # Complete the solve function below. def count(n, p): count = 0 n_copy = n while n_copy > 1: count += n_copy // p n_copy //= p return count def solve(n): pr = 1 isprime = [True] * (n + 1) for num in range(2, n + 1): if not isprime[num]: continue pr = pr * (2 * count(n, num) + 1) % 1000007 for multiple in range(2 * num, n + 1, num): isprime[multiple] = False return pr if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') n = int(input()) result = solve(n) fptr.write(str(result) + '\n') fptr.close()
+ 1 comment hint: in order to see the "divisors of n!^2" thing, do not complete the partial fractions, e.g. 1/x + 1/y = xy/(x+y). that doesn't help all. Instead, solve for x.
also, from the editorial, the proof that y-n! cannot be negative is kind of glossed over and slightly nontrivial. It can be done by starting from x>0 and showing that y-n!<0 would lead to a contradiction.
+ 1 comment The key point is that the number of positive integral solutions of the given equation is equal to the number of factors of (n!)^2. (Hint: rearrage the equation. You may need to check out Diophantine Equation)
Another important point is to compute the number of factors of (n!)^2 with a good time complexity. It turns out that you could build each factor from the more fundamental element: the prime factors of (n!)^2. (Hint: determine all the prime factors of (n!)^2, which is all the prime numbers not greater than n, and their number of appearances)
Once you have all the prime factors of (n!)^2 and their number of appearances, the last step is just a simple Combinatorial Counting Problem.
+ 3 comments Because I personally think that small answers help clarify "what is the question", which is important. These answers shouldn't give a hint about the solution. f(0) = 1; f(1) = 1; f(2) = 3; f(3) = 9
Sort 38 Discussions, By:
Please Login in order to post a comment