NC50562. 聪明的燕姿
描述
输入描述
输入包含k组数据。
对于每组数据，输入包含一个号码牌S。
输出描述
对于每组数据，输出有两行，第一行包含一个整数m，表示有m个等的人。
第二行包含相应的m个数，表示所有等的人的号码牌。
注意：你输出的号码牌必须按照升序排列。
示例1
输入:
42
输出:
3 20 26 41
C++11(clang++ 3.9) 解法, 执行用时: 252ms, 内存消耗: 2696K, 提交时间: 2020-06-01 23:01:15
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50000;
int vis[N],prime[N+5],tot=0,cnt=0;
int ans[100000];
void get()
{
memset(vis,0,sizeof(vis));
for(int i=2;i<=N;i++)
{
if(!vis[i])
prime[++tot]=i;
for(int j=1;j<=tot&&prime[j]*i<=N;j++)
{
vis[prime[j]*i]=1;
if(i%prime[j]==0)
break;
}
}
vis[1]=1;
}
int isprime(ll x)
{
if(x<=N)
return 1-vis[x];
for(ll i=2;i*i<=x;i++)
if(x%i==0)
return 0;
return 1;
}
void dfs(ll now,int x,ll t)
{
if(now==1)
{
ans[++cnt]=t;
return;
}
if(now-1>=prime[x]&&isprime(now-1))
ans[++cnt]=(now-1)*t;
int i;
ll j,tmp;
for(i=x;i<=tot&&prime[i]*prime[i]<=now;i++)
{
j=prime[i]+1;
tmp=prime[i];
for(;j<=now;tmp*=prime[i],j+=tmp)
if(now%j==0)
dfs(now/j,i+1,t*tmp);
}
}
int main()
{
get();
ll s;
while(~scanf("%lld",&s))
{
cnt=0;
dfs(s,1,1ll);
sort(ans+1,ans+1+cnt);
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
printf("%d ",ans[i]);
if(cnt)
puts("");
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 233ms, 内存消耗: 2680K, 提交时间: 2019-08-23 10:23:43
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50000;
int vis[N],prime[N+5],tot=0,cnt=0;
int ans[100000];
void get(){
memset(vis,0,sizeof(vis));
for(int i=2;i<=N;i++){
if(!vis[i])
prime[++tot]=i;
for(int j=1;j<=tot&&prime[j]*i<=N;j++){
vis[prime[j]*i]=1;
if(i%prime[j]==0)
break;
}
}
vis[1]=1;
}
int isprime(ll x){
if(x<=N)
return 1-vis[x];
for(ll i=2;i*i<=x;i++)
if(x%i==0)
return 0;
return 1;
}
void dfs(ll now,int x,ll t){
if(now==1){
ans[++cnt]=t;
return;
}
if(now-1>=prime[x]&&isprime(now-1))
ans[++cnt]=(now-1)*t;
int i;
ll j,tmp;
for(i=x;i<=tot&&prime[i]*prime[i]<=now;i++){
j=prime[i]+1;
tmp=prime[i];
for(;j<=now;tmp*=prime[i],j+=tmp)
if(now%j==0)
dfs(now/j,i+1,t*tmp);
}
}
int main(){
get();
ll s;
while(~scanf("%lld",&s)){
cnt=0;
dfs(s,1,1ll);
sort(ans+1,ans+1+cnt);
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
printf("%d ",ans[i]);
if(cnt)
puts("");
}
return 0;
}