SPOJ Equation :求 1/n!=1/x+1/y 的解的个数

发布时间:2017-1-23 22:40:43 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"SPOJ Equation :求 1/n!=1/x+1/y 的解的个数",主要涉及到SPOJ Equation :求 1/n!=1/x+1/y 的解的个数方面的内容,对于SPOJ Equation :求 1/n!=1/x+1/y 的解的个数感兴趣的同学可以参考一下。

题目地址:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29547#problem/M 解析: 题目就是求1/n! = 1/x + 1/y 的解的个数,看样例知要考虑(x,y)对数的关系。 设 m=n! ,由等式知x,y必定大于n!,所以再设 x=n!+k=m+k 带入 1/m=1/x+1/y 中化简得到y=m*m/k+m,因y为整数,所以要求k整除m*m,即k为m*m的因子,问题便转化为求n!*n!的因子个数, 设n!=p1^e1 * p2^e2 * p3^e3 *...*pk^ek,则 n!*n!= p1^(2*e1) * p2^(2*e2) *...*pk^(2*ek) 。 则因子个数sum=(2*e1+1)*(2*e2+1)*...*(2*ek+1); 答案很大,需要高精度。用java处理方便! import java.util.*; import java.math.*; public class Main { static int N = 10050; static int q = 0; static int prime[] = new int[N]; public static void sieve_prime( ){ int i; int flag[] = new int [N]; for (i = 2; i * i < N; i++) { if (flag[i] == 0) prime[q++] = i; for (int j = i * i; j < N; j += i) { flag[j] = 1; } } for (; i < N; i++) if (flag[i] == 0) prime[q++] = i; } public static void solve(int n) { BigInteger ans = BigInteger.valueOf(1); int temp,count; for (int i = 0; prime[i]<= n && i < q && n > 1; i++) { count = 0; temp= prime[i]; while (temp <= n) { count+=n/temp; temp*=prime[i]; } ans = ans.multiply(BigInteger.valueOf(count * 2 + 1)); } System.out.println(ans); } public static void main(String[] args) { Scanner in = new Scanner(System.in); sieve_prime(); int x; while (in.hasNext()) { x = in.nextInt(); if (x == 0) break; solve(x); } in.close(); } }

上一篇:[置顶] 谈谈程序员创业的一些事情
下一篇:CPU时间片

相关文章

相关评论