WA 40pts求调
查看原帖
WA 40pts求调
502314
Just_A_Sentence楼主2025/7/21 07:44
#include<bits/stdc++.h>
using namespace std;
int a[1000005],tot=0,totb=0;
int np[100005],prime[100005],num=0;
void init(){
	np[1]=1;
	for(int i=2;i<=100000;i++){
		if(!np[i]){
			prime[++num]=i;
			if(1ll*i*i>100000) continue;
			for(int j=i*i;j<=100000;j+=i) np[j]=1;
		}
	}
}
bool isprime(int x){
	if(x<=1) return 0;
	for(int i=2;i*i<=x;i++){
		if(x%i==0) return 0;
	}
	return 1;
}
void dfs(long long x,long long ans,int pre){
	if(isprime(x-1)&&x>pre) a[++tot]=(x-1)*ans;
	if(x==1){
		a[++tot]=ans;
		return;
	}
	for(int i=1;i<=num&&1ll*prime[i]*prime[i]<=x;i++){
		if(prime[i]<=pre) continue;
		long long cmp=prime[i],sum=1;
		while(cmp+sum<=x){
			sum+=cmp;
			if(x%sum==0) dfs(x/sum,ans*cmp,prime[i]);
			cmp*=prime[i];
		}
	}
}
int main(){
	init();
	long long n;
	while(cin>>n){
		memset(a,0,sizeof(a));
		tot=0;
		totb=0;
		dfs(n,1,0);
		sort(a+1,a+tot+1);
		printf("%d\n",tot);
		if(tot==0) continue;
		for(int i=1;i<=tot;i++){
			printf("%d ",a[i]);
		}
		printf("\n");
	}
	return 0;
}
2025/7/21 07:44
加载中...