The question is, how to solve 1/x + 1/y = 1/N! (N factorial). Find the number of values that satisfy x and y for large values of N.
问题是，如何解1/x + 1/y = 1/N!(N的阶乘)。找到满足x和y的值的值，以满足N的大值。
I've solved the problem for relatively small values of N (any N! that'll fit into a long). So, I know I solve the problem by getting all the divisors of (N!)^2. But that starts failing when (N!)^2 fails to fit into a long. I also know I can find all the divisors of N! by adding up all the prime factors of each number factored in N!. What I am missing is how I can use all the numbers in the factorial to find the x and y values.
我已经解决了相对小的N值的问题(任何N!那将会很长。所以,我知道我解决问题,让所有(N !)^ 2的因数。但开始时失败(N !)^ 2未能适应很长。我也知道我能找到N的所有因数!通过把N中每个数的所有质数因子加起来。我所缺少的是如何使用factorial中的所有数字来找到x和y值。
EDIT: Not looking for the "answer" just a hint or two.
编辑:不寻找“答案”只是一两个提示。
5 个解决方案
#1
11
Here is your hint. Suppose that m = p1k1 · p2k2 · ... · pjkj. Every factor of m will have from 0 to k1 factors of p1, 0 to k2 factors of p2, and so on. Thus there are (1 + k1) · (1 + k2) · ... · (1 + kj) possible divisors.
这是你的暗示。假设m = p1k1·p2k2·…·pjkj。m的每一个因子都是从0到k1因子p1, 0到k2因子p2，等等。因此有(1 + k1)·(1 + k2)·…·(1 + kj)可能的除数。
So you need to figure out the prime factorization of n!2.
所以你需要算出n的质因数分解。
Note, this will count, for instance, 1⁄6 = 1⁄8 + 1⁄24 as being a different pair from 1⁄6 = 1⁄24 + 1⁄8. If order does not matter, add 1 and divide by 2. (The divide by 2 is because typically 2 divisors will lead to the same answer, with the add 1 for the exception that the divisor n! leads to a pair that pairs with itself.)
注意,这将计数,例如,1⁄6 = 1⁄8 + 1⁄24是一对不同从1⁄6 = 1⁄24 + 1⁄8。如果顺序无关紧要，加1并除以2。(除以2，因为通常2个因子会导致相同的答案，除了除数n之外，加1)导致一对与自身配对。
#2
21
Problem : To find the count of factors of (N!)^2.
问题:找到数(N !)^ 2的因素。
Hints :
提示:
1) You don't really need to compute (N!)^2 to find its prime factors. Why? Say you find the prime factorization of N! as (p1^k1) x (p2^k2) .... (pi^ki) where pj's are primes and kj's are exponents.
1)你真的不需要计算(N !)^ 2找到其主要因素。为什么?说你找到了N的质因数分解!(p1 ^ k1)x(p2 ^ k2)....(pi ki) pj是质数，而kj是指数。
Now the number of factors of N! is as obvious as (k1 + 1) x (k2 + 1) x ... x (ki + 1).
现在N的因数个数!很明显(k1 + 1) x (k2 + 1) x…x(ki + 1)。
2) For (N!)^2, the above expression would be, (2*k1 + 1) * (2*k2 + 1) * .... * (2*k1 + 1) which is essentially what we are looking for.
2)(N)^ 2,上面的表达式,(2 * k1 + 1)*(2 * k2 + 1)* ....* (2*k1 + 1)这就是我们要找的。
For example, lets take N=4, N! = 24 and (N!)^2 = 576; 24 = 2^3 * 3^1; Hence no of factors = (3+1) * (1+1) = 8, viz {1,2,3,4,6,8,12,24} For 576 = 2^6 * 3^2, it is (2*3 + 1) * (2*1 + 1) = 21;
例如，让N=4, N!= 24(N !)^ 2 = 576;24 = 2 ^ 3 * 3 ^ 1;因此没有因素=(3 + 1)*(1 + 1)= 8,即{ 1、2、3、4、6、8、12、24 } 576 = 2 ^ 6 * 3 ^ 2,它是(2 * 3 + 1)*(2 * 1 + 1)= 21;
3) Basically you need to find the multiplicity of each primes <= N here.
3)基本上，你需要在这里找到每个素数的多样性。
Please correct me if i'm wrong somewhere till here.
如果我在什么地方错到这里，请纠正我。
#3
3
It's more to math than programming. Your equation implies xy = n!(x+y).
数学比编程更重要。你的方程意味着xy = n!(x+y)
Let c = gcd(x,y), so x = cx', y= cy', and gcd(x', y')=1. Then c^2 x' y'=n! c (x'+y'), so cx'y' = n!(x' + y').
让c =肾小球囊性肾病(x,y),所以x =残雪,y = cy,和肾小球囊性肾病(x,y)= 1。然后c ^ 2 x y = n !c (x'+y')，所以cx'y' = n!(x + y)。
Now, as x' and y' are coprime, and cannot be divisible be x'+y', c should be. So c = a(x'+y'), which gives ax'y'=n!.
现在，x'和y'是coprime，不能被分割成x'+y'， c应该是。所以c = a(x'+y')得到ax' =n!
To solve your problem, you should find all two coprime divisors of n!, every pair of which will give a solution as ( n!(x'+y')/y', n!(x'+y')/x').
为了解决你的问题，你应该找到n的所有的2个coprime因子!每一对都给出一个解(n!(x'+y')/y'， n!(x'+y')/x')。
#4
2
Let F(N) be the number of (x,y) combinations that satisfy your requirements.
让F(N)为满足要求的(x,y)组合的数目。
F(N+1) = F(N) + #(x,y) that satisfy the condition for N+1 and at least one of them (x or y) is not divisible N+1.
F(N+1) = F(N) + #(x,y)满足N+1的条件，其中至少有一个(x或y)不能被整除N+1。
The intuition here is for all combinations (x,y) that work for N, (x*(N+1), y*(N+1)) would work for N+1. Also, if (x,y) is a solution for N+1 and both are divisible by n+1, then (x/(N+1),y/(N+1)) is a solution for N.
这里的直觉是，对于N的所有组合(x,y)， (x*(N+1)， y*(N+1))对于N+1是成立的。同样，如果(x,y)是N+1的解，它们都能被N+1整除，那么(x/(N+1)，y/(N+1))是N的解。
Now, I am not sure how difficult it is to find #(x,y) that work for (N+1) and at least one of them not divisible by N+1, but should be easier than solving the original problem.
现在，我不知道找到(N+1)的#(x,y)是多么困难，至少其中一个不能被N+1整除，但应该比解原来的问题容易。
#5
2
Now Multiplicity or Exponent for Prime p in N! can be found by below formula:\ Exponent of P in (N!)= [N/p] + [N/(P^2)] +[N/(P^3)] + [N/(P^4)] +...............
现在，在N中，质数p的多重性或指数。可以由下面的公式:\指数的P(N !)=[N / P]+[N / P(^ 2)]+[N / P(^ 3)]+[N / P(^ 4)]+ ...............
where [x]=Step function E.g. [1.23]=integer part(1.23)=1
E.g. Exponent of 3 in 24! = [24/3] +[24/9]+ [24/27] + ... = 8 +2 +0 + 0+..=10 Now whole problem reduces to identifying prime number below N and finding its Exponent in N!
指数为3 / 24!=[24/3]+[24/9]+[24/27]+…= 8 +2 +0 +0 +。=10现在整个问题减少到找出N以下的质数并在N中找到它的指数!
#1
11
Here is your hint. Suppose that m = p1k1 · p2k2 · ... · pjkj. Every factor of m will have from 0 to k1 factors of p1, 0 to k2 factors of p2, and so on. Thus there are (1 + k1) · (1 + k2) · ... · (1 + kj) possible divisors.
这是你的暗示。假设m = p1k1·p2k2·…·pjkj。m的每一个因子都是从0到k1因子p1, 0到k2因子p2，等等。因此有(1 + k1)·(1 + k2)·…·(1 + kj)可能的除数。
So you need to figure out the prime factorization of n!2.
所以你需要算出n的质因数分解。
Note, this will count, for instance, 1⁄6 = 1⁄8 + 1⁄24 as being a different pair from 1⁄6 = 1⁄24 + 1⁄8. If order does not matter, add 1 and divide by 2. (The divide by 2 is because typically 2 divisors will lead to the same answer, with the add 1 for the exception that the divisor n! leads to a pair that pairs with itself.)
注意,这将计数,例如,1⁄6 = 1⁄8 + 1⁄24是一对不同从1⁄6 = 1⁄24 + 1⁄8。如果顺序无关紧要，加1并除以2。(除以2，因为通常2个因子会导致相同的答案，除了除数n之外，加1)导致一对与自身配对。
#2
21
Problem : To find the count of factors of (N!)^2.
问题:找到数(N !)^ 2的因素。
Hints :
提示:
1) You don't really need to compute (N!)^2 to find its prime factors. Why? Say you find the prime factorization of N! as (p1^k1) x (p2^k2) .... (pi^ki) where pj's are primes and kj's are exponents.
1)你真的不需要计算(N !)^ 2找到其主要因素。为什么?说你找到了N的质因数分解!(p1 ^ k1)x(p2 ^ k2)....(pi ki) pj是质数，而kj是指数。
Now the number of factors of N! is as obvious as (k1 + 1) x (k2 + 1) x ... x (ki + 1).
现在N的因数个数!很明显(k1 + 1) x (k2 + 1) x…x(ki + 1)。
2) For (N!)^2, the above expression would be, (2*k1 + 1) * (2*k2 + 1) * .... * (2*k1 + 1) which is essentially what we are looking for.
2)(N)^ 2,上面的表达式,(2 * k1 + 1)*(2 * k2 + 1)* ....* (2*k1 + 1)这就是我们要找的。
For example, lets take N=4, N! = 24 and (N!)^2 = 576; 24 = 2^3 * 3^1; Hence no of factors = (3+1) * (1+1) = 8, viz {1,2,3,4,6,8,12,24} For 576 = 2^6 * 3^2, it is (2*3 + 1) * (2*1 + 1) = 21;
例如，让N=4, N!= 24(N !)^ 2 = 576;24 = 2 ^ 3 * 3 ^ 1;因此没有因素=(3 + 1)*(1 + 1)= 8,即{ 1、2、3、4、6、8、12、24 } 576 = 2 ^ 6 * 3 ^ 2,它是(2 * 3 + 1)*(2 * 1 + 1)= 21;
3) Basically you need to find the multiplicity of each primes <= N here.
3)基本上，你需要在这里找到每个素数的多样性。
Please correct me if i'm wrong somewhere till here.
如果我在什么地方错到这里，请纠正我。
#3
3
It's more to math than programming. Your equation implies xy = n!(x+y).
数学比编程更重要。你的方程意味着xy = n!(x+y)
Let c = gcd(x,y), so x = cx', y= cy', and gcd(x', y')=1. Then c^2 x' y'=n! c (x'+y'), so cx'y' = n!(x' + y').
让c =肾小球囊性肾病(x,y),所以x =残雪,y = cy,和肾小球囊性肾病(x,y)= 1。然后c ^ 2 x y = n !c (x'+y')，所以cx'y' = n!(x + y)。
Now, as x' and y' are coprime, and cannot be divisible be x'+y', c should be. So c = a(x'+y'), which gives ax'y'=n!.
现在，x'和y'是coprime，不能被分割成x'+y'， c应该是。所以c = a(x'+y')得到ax' =n!
To solve your problem, you should find all two coprime divisors of n!, every pair of which will give a solution as ( n!(x'+y')/y', n!(x'+y')/x').
为了解决你的问题，你应该找到n的所有的2个coprime因子!每一对都给出一个解(n!(x'+y')/y'， n!(x'+y')/x')。
#4
2
Let F(N) be the number of (x,y) combinations that satisfy your requirements.
让F(N)为满足要求的(x,y)组合的数目。
F(N+1) = F(N) + #(x,y) that satisfy the condition for N+1 and at least one of them (x or y) is not divisible N+1.
F(N+1) = F(N) + #(x,y)满足N+1的条件，其中至少有一个(x或y)不能被整除N+1。
The intuition here is for all combinations (x,y) that work for N, (x*(N+1), y*(N+1)) would work for N+1. Also, if (x,y) is a solution for N+1 and both are divisible by n+1, then (x/(N+1),y/(N+1)) is a solution for N.
这里的直觉是，对于N的所有组合(x,y)， (x*(N+1)， y*(N+1))对于N+1是成立的。同样，如果(x,y)是N+1的解，它们都能被N+1整除，那么(x/(N+1)，y/(N+1))是N的解。
Now, I am not sure how difficult it is to find #(x,y) that work for (N+1) and at least one of them not divisible by N+1, but should be easier than solving the original problem.
现在，我不知道找到(N+1)的#(x,y)是多么困难，至少其中一个不能被N+1整除，但应该比解原来的问题容易。
#5
2
Now Multiplicity or Exponent for Prime p in N! can be found by below formula:\ Exponent of P in (N!)= [N/p] + [N/(P^2)] +[N/(P^3)] + [N/(P^4)] +...............
现在，在N中，质数p的多重性或指数。可以由下面的公式:\指数的P(N !)=[N / P]+[N / P(^ 2)]+[N / P(^ 3)]+[N / P(^ 4)]+ ...............
where [x]=Step function E.g. [1.23]=integer part(1.23)=1
E.g. Exponent of 3 in 24! = [24/3] +[24/9]+ [24/27] + ... = 8 +2 +0 + 0+..=10 Now whole problem reduces to identifying prime number below N and finding its Exponent in N!
指数为3 / 24!=[24/3]+[24/9]+[24/27]+…= 8 +2 +0 +0 +。=10现在整个问题减少到找出N以下的质数并在N中找到它的指数!