| ||||||||||
| 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