当数越来越大时欧拉函数很大,与因子数差距越来越大,所以当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; }