Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
网上没找到java的,在这里贴下Java代码。 RE了一个小时终于过了。。。带注释import java.util.*; public class Main{ // n是2的20次方加1 static final int n = 1048577; // nums数组用于生成质数。和generate_primes配套使用 static boolean nums[] = new boolean[n]; // primes储存了生成出来的所有质数 static ArrayList<Integer> primes = new ArrayList<Integer>(); // yinshu储存了当前输入数字的所有质数因数 static ArrayList<Integer> yinshu = new ArrayList<Integer>(); // C是计算组合中的重复值 static long C; // 生成质数算法 static void generate_primes(){ for(int i = 0; i < n; i++) nums[i] = true; nums[0] = nums[1] = false; for(int i = 2; i < n; i++){ if(nums[i]){ primes.add(i); for(int j = 2*i; j < n; j += i){ nums[j] = false; } } } } // 因数分解算法 static void ysfj(int c){ int index1 = 0; int mi = 0; while(c > 1){ int pr = primes.get(index1); if(c%pr == 0){ mi++; // mi是当前因数的幂。 // 比如说16=2*2*2*2,那C=1*2*3*4 // 比如说500=2*2*5*5*5,那C=1*2*1*2*3 C *= mi; yinshu.add(pr); c/= pr; }else{ mi = 0; index1++; } } } // 阶乘算法 static long jc(int n){ long ans = 1; while(n-->1) ans *= n+1; return ans; } public static void main(String[] args) { Scanner s = new Scanner(System.in); // 只生成1次质数(你也可以靠打表来刷排行榜。。。) generate_primes(); while(s.hasNext()){ // 如果输入的X是质数,直接输出1 1 int X = s.nextInt(); if(nums[X]){ System.out.println("1 1"); continue; } yinshu.clear(); C = 1; ysfj(X); // 第一个答案ans1就是质因数的数量 int ans1 = yinshu.size(); long ans2 = 1; // 第二个答案就是ans1的阶乘(排列),除去重复的数字C(组合) ans2 = jc(ans1) / C; System.out.println(ans1+" "+ans2); } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator