栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

聪明的燕姿 搜索dfs 约数之和 java

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

聪明的燕姿 搜索dfs 约数之和 java

城市中人们总是拿着号码牌,不停寻找,不断匹配,可是谁也不知道自己等的那个人是谁。

可是燕姿不一样,燕姿知道自己等的人是谁,因为燕姿数学学得好!

燕姿发现了一个神奇的算法:假设自己的号码牌上写着数字 S,那么自己等的人手上的号码牌数字的所有正约数之和必定等于 S。

所以燕姿总是拿着号码牌在地铁和人海找数字(喂!这样真的靠谱吗)。

可是她忙着唱《绿光》,想拜托你写一个程序能够快速地找到所有自己等的人。

输入格式
输入包含 k 组数据。

对于每组数据,输入包含一个号码牌 S。

输出格式
对于每组数据,输出有两行。

第一行包含一个整数 m,表示有 m 个等的人。

第二行包含相应的 m 个数,表示所有等的人的号码牌。

注意:你输出的号码牌必须按照升序排列。

数据范围
1≤k≤100,
1≤S≤2×109
输入样例:
42
输出样例:
3
20 26 41

import java.util.*;

public class Main
{
	static int N=50000,len;
	
	static int prime[]=new int [N],cnt;
	static boolean st[]=new boolean [N];
	
	static int a[]=new int [N];
	
	static boolean is_prime(int x)
	{
		if(x(last==-1?1:prime[last])&&is_prime(s-1))dfs(s-1,prod*(s-1),1);
		
		for(int i=last+1;prime[i]<=s/prime[i];++i)
		{
			 int p=prime[i];
			 for(int j=p+1,t=p;j<=s;t*=p,j+=t)
			 {
				 if(s%j==0)
				 {
					 dfs(i,prod*t,s/j);
				 }
			 }
		}
		
	}
	
	static void getp(int n)
	{
		for(int i=2;i<=n;++i)
		{
			if(st[i]==false)prime[cnt++]=i;
			for(int j=0;prime[j]*i<=n;++j)
			{
				st[prime[j]*i]=true;
				if(i%prime[j]==0)break;
			}
		}
	}
	
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		getp(N-1);
		while(sc.hasNext())
		{
			int s;
			len=0;
			s=sc.nextInt();
			dfs(-1,1,s);
			System.out.println(len);
			Arrays.sort(a,0,len);
			for(int i=0;i
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/727192.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号