当数越来越大时欧拉函数很大,与因子数差距越来越大,所以当n达到一定值时就找不到相等的区间了
暴力模拟了前500,30以后都是10
#include<stdio.h>
int main()
{
int a[31]={0,1,1,2,2,4,5,5,6,6,7,7,7,7,7,7,7,7,8,8,8,8,8,8,9,9,9,9,9,9,10};
int n,t,op=1;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("Case %d: ",op++);
if(n>=30)
printf("%d\n",a[30]);
else printf("%d\n",a[n]);
}
return 0;
}
阅读全文