首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。