c*******n
发帖数: 63 | 1 http://www.interviewstreet.com
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.
1 <= N <= 10^6
我一开始以为这题单纯是大数运算的问题，后来发现似乎不是
觉得解题的突破点应该是：
let p = n! --> 1/p - 1/(p+k) = k/(p(p+k))
p(p+k)/k is an integer, 1<= k <= p and the total solution of k is the unique
number of products of all combination of [1, n],
that is 1Cn + 2Cn + .... + (n-1)Cn + nCn - redundant products = 2^n -
redundant products
所以问题转成找重复乘积了
比如
6！重复的有 6, 2*3; 3*4, 2*6 等等
想不出什么好思路，各位大牛有没有什么想法 | b**********r
发帖数: 91 | 2 It requires a little bit basic number theory:
The solution of the equation is in the following format:
x=N!+m, y = N!+N!^2/m
where m | (N!)^2
so the total number of solutions are the (number of factors of (N!)^2)-1
(
the minus 1 is for the case x=2*N! and y=2*N!, which is double counted)
Lemma 1: let M = p1^a1*p2*a2*...*pk^ak
where p1, p2, .. pk are distincted prime numbers, a1, a2, ... ak are
positive integers, then the number of factors of M is (a1+1)*(a2+1)*...*
(ak+
1)
Lemma 2: let p be a prime number and p < N, then the largest ap for
p^ap|N!
is the following:
[N/p]+[N/p^2]+....+[N/p^w] where p^w <= N and p^(w+1) > N
where [x] is the integer part of x
Based on the above two lemmas, the algorithms can be implemented in the
following way:
(1) for a given N, find all the prime numbers less or equal to N
(2) For each prime number p obtained from (1), calculate the ap by lemma
2.
then the total number solutions can be obtained with Lemma 1.
(1/y)
=
of
unique
【在 c*******n 的大作中提到】
: http://www.interviewstreet.com
: 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.
: 1 <= N <= 10^6
: 我一开始以为这题单纯是大数运算的问题，后来发现似乎不是
: 觉得解题的突破点应该是：
: let p = n! --> 1/p - 1/(p+k) = k/(p(p+k))
: p(p+k)/k is an integer, 1<= k <= p and the total solution of k is the unique
: number of products of all combination of [1, n],
|
|
