首页 > 代码库 > HDU-1286-找新朋友
HDU-1286-找新朋友
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1286
题目做的很乱，很不应该，
开始我直接暴力超时
超时代码
#include<stdio.h>
int main()
{
int gy(int x,int y);
int c,n,k,i;
scanf("%d",&c);
while(c--)
{
k=0;
scanf("%d",&n);
for(i=2;i<n;i++)
{
if(gy(i,n))
k++;
}
printf("%d\n",n-k-1);
}
return 0;
}
int gy(int x,int y)
{
int i;
for(i=2;i<=x;i++)
{
if(x%i==0&&y%i==0)
return 1;
}
return 0;
}
思路明显不怎么好
AC代码
#include<stdio.h>
#include<math.h>
#include<string.h>
int main(void)
{
int n,t,s,i,j;
int hash[40000];
scanf("%d",&t);
while(t--)
{
memset(hash,0,sizeof(hash));
scanf("%d",&n);
int k=n/2;
for(i=2;i<=k+1;i++)
{
if(n%i==0)
{
for(j=1;i*j<n;j++)
hash[i*j]++;
}
}
s=0;
for(i=2;i<n;i++)
if(hash[i])
s++;
printf("%d\n",n-s-1);
}
return 0;
}
敢想，想到就敲，别犹豫。
HDU-1286-找新朋友
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。