pta 1096 大美数 (15 分)

2022-01-09 00:47

1096 大美数 (15 分)


若正整数  可以整除它的 4 个不同正因数之和,则称这样的正整数为“大美数”。本题就要求你判断任一给定的正整数是否是“大美数”。

输入格式:

输入在第一行中给出正整数 k<=10,随后一行给出k个待检测的、不超过10^4的正整数

输出格式:

对每个需要检测的数字,如果它是大美数就在一行中输出 Yes,否则输出 No


输入样例:

3

18 29 40


输出样例:

Yes
No

Yes




解题思路:

        这题很有意思,我第一眼以为要把约数都求出来,然后深度遍历。后来想想也不一定要用,四重循环也可以。但是怎么取约数是有讲究的。很多人习惯取约数,按照素数的循环来求,这可不行哦。

        首先我们看题意。什么叫整除。例如a%b==0  叫a被b整除,换言之b整除a。也就说题意要求我们把四个不同的约数之和对我们输入的整数取余。。而不是反过来的,我看网上大多数都写错了。

        还有更重要的是,既然是和对输入整数取余,那就可以覆盖n倍,n是可以大于一,意味着我们输入的整数本身也可以是约数。这个不要忘记,


代码:

#include
int main()
{
int n,m,i,j,count,k,o,p,flag;
scanf("%d",&n);
int a[200]; //约数个数,这个是怎么估计的呢是因为我们取根号乘2。
for(i=0;i {
count=0;
flag=0;
scanf("%d",&m);
for(j=1;j<=m;j++)
{
if(m%j==0)
{
a[count++]=j;
}
}
if(count<4) //约数都小于四个就肯定不是了。我当时怕超时。提前判断一点。
{
    printf("No\n");
    continue;
}
for(j=0;j {
for(k=j+1;k for(o=k+1;o for(p=o+1;p {
if((a[j]+a[k]+a[o]+a[p])%m==0)
{
flag=1;
break;
}
}
}
out:
if(!flag)
printf("No\n");
else
printf("Yes\n");

}

return 0;
}


浏览 53
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报