did anyone buy an antique home?# Living
c*n
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 等等
想不出什么好思路,各位大牛有没有什么想法
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 等等
想不出什么好思路,各位大牛有没有什么想法