AcWing 1296. 聪明的燕姿(Java)
原题链接
中等
作者:
上杉
,
2021-04-12 19:35:04
,
所有人可见
,
阅读 412
import java.util.*;
public class Main{
static int N = 500000;//因为我们特判了S = 1 + P的情况,所以最大S = P^2,所以50万够了
static int[] primes = new int[N];
static int cnt;
static boolean[] flag = new boolean[N];
static int[] res = new int[N];//存放每一组数据的答案
static int len;//存放每一组数据的答案个数
public static void main(String[] args){
getPrimes(N - 1);//素数筛
Scanner input = new Scanner(System.in);
while(input.hasNextInt()){
int S = input.nextInt();
dfs(-1,1,S);
Arrays.sort(res,0,len);
System.out.println(len);
if(len != 0){
for(int i = 0 ; i < len ; i++){
System.out.print(res[i] + " ");
}
System.out.println();
len = 0;
}
}
}
public static void dfs(int last,int product,int S){
if(S == 1){
// System.out.println(product);
res[len++] = product;
return;
}
int pre = last >= 0 ? primes[last] : 1;
if(S - 1 > pre && isPrime(S-1)){
//特判S - 1是不是质数,即存不存在 S= (1 + P) *某个数的情况,因为我们素数没有枚举到S-1.
//所以这种情况需要特判
res[len++] = product * (S - 1);
}
for(int i = last + 1 ; primes[i] <= S / primes[i] ; i++){
//初始还是需要枚举 1 + P的情况,因为当P很小的时候,可能不符合上面但是dfs下去是正确答案
int p = primes[i];
for(int j = 1 + p ; j <= S ; p *= primes[i],j+=p){
//循环判断 1+p、1+p+p^2
if(S % j == 0){
dfs(i,product * p, S / j);
}
}
}
}
public static void getPrimes(int n){
for(int i = 2 ; i <= n ; i++){
if(!flag[i]){
primes[cnt++] = i;
}
for(int j = 0 ; primes[j] * i <= n ; j++){
flag[primes[j] * i] = true;
if(i % primes[j] == 0)break;
}
}
}
public static boolean isPrime(int X){
if(X < N)return !flag[X];
for (int i = 0; primes[i] <= X / primes[i]; i++) {
if(X % primes[i] == 0)return false;
}
return true;
}
}