pta 1096 大美數(shù) (15 分)
1096 大美數(shù) (15 分)
若正整數(shù)??可以整除它的 4 個(gè)不同正因數(shù)之和，則稱這樣的正整數(shù)為“大美數(shù)”。本題就要求你判斷任一給定的正整數(shù)是否是“大美數(shù)”。
輸入格式：
輸入在第一行中給出正整數(shù) k<=10，隨后一行給出k個(gè)待檢測(cè)的、不超過(guò)10^4的正整數(shù)
輸出格式：
對(duì)每個(gè)需要檢測(cè)的數(shù)字，如果它是大美數(shù)就在一行中輸出?Yes，否則輸出?No。
輸入樣例：
318 29 40
輸出樣例：
Yes
NoYes
解題思路：
????????這題很有意思，我第一眼以為要把約數(shù)都求出來(lái)，然后深度遍歷。后來(lái)想想也不一定要用，四重循環(huán)也可以。但是怎么取約數(shù)是有講究的。很多人習(xí)慣取約數(shù)，按照素?cái)?shù)的循環(huán)來(lái)求，這可不行哦。
????????首先我們看題意。什么叫整除。例如a%b==0? 叫a被b整除，換言之b整除a。也就說(shuō)題意要求我們把四個(gè)不同的約數(shù)之和對(duì)我們輸入的整數(shù)取余。。而不是反過(guò)來(lái)的，我看網(wǎng)上大多數(shù)都寫錯(cuò)了。
????????還有更重要的是，既然是和對(duì)輸入整數(shù)取余，那就可以覆蓋n倍，n是可以大于一，意味著我們輸入的整數(shù)本身也可以是約數(shù)。這個(gè)不要忘記，
代碼：
#include
int main()
{
int n,m,i,j,count,k,o,p,flag;
scanf("%d",&n);
int a[200]; //約數(shù)個(gè)數(shù)，這個(gè)是怎么估計(jì)的呢是因?yàn)槲覀內(nèi)「?hào)乘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) //約數(shù)都小于四個(gè)就肯定不是了。我當(dāng)時(shí)怕超時(shí)。提前判斷一點(diǎn)。
{
????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;
}
評(píng)論
圖片
表情