首页 > 代码库 > math3090

math3090

题意:从(0,0)点往其他点连线,中间不能经过任何点,问最多连多少条。。

自己AC通过 哈哈

中间没有其他的点的即为互为质数的情况,比如(2,4)不满足条件,因为两者存在公约数2,因此(1,2)也在(2,4)这条线上,而比如(5,8)两者互为质数这条直线上不存在其他整数点

#include<cstdio>

#include<cstring>

 

int ss[1002];

 

int euler(int m)

{

int j,res;

res=m;

 

for(j=2;j*j<=m;j++)//m可以逐渐减小的

{

if(m%j==0)

{

res=res-res/j;

while(m%j==0)

m=m/j;//m可以逐渐减小的

}

}

if(m>1)

res=res-res/m;

 

return res;

}

 

int main()

{

int i,j,t,num,sum;

memset(ss,0,sizeof(ss));

 

for(i=1;i<=1000;i++)

ss[i]=euler(i);

 

scanf("%d",&t);

for(j=1;j<=t;j++)

{

sum=0;

scanf("%d",&num);

 

for(i=2;i<=num;i++)

sum+=ss[i];

 

sum=sum*2;

 

sum+=3;

 

printf("%d %d %d\n",j,num,sum);

}

return 1;

}

math3090