统计分母在区间[a,b]的最简真分数共有多少个?并求这些最简真分数升序序列中的第k项。
所谓最简真分数是指:分子小于分母,且分子分母无公因数的分数。
输入要求 输入正整数a,b,k。 输出要求 输出分2行:第1行是最简真分数的个数;第2行是递增序列中第k项的分数形式。 输入样例 10 99 1000 输出样例 n=2976The 1000 Item=27/80 提示 分数项不超过3000个 代码实现 #include<stdio.h>struct test{ int fenmu; int fenzi;};int main(){ test p[3000]; test h; int a,b,k=0,n=0; int i,j; int t,u; scanf("%d%d",&a,&b); scanf("%d",&k); for(j=a;j<=b;j++) for(i=1;i<=j-1;i++) { for(t=0,u=2;u<=i;u++) if(j%u==0&&i%u==0) { t=1;break; } if(t==0){n++;p[n].fenzi=i;p[n].fenmu=j;} } for(i=1;i<=n-1;i++) for(j=1;j<=n-i;j++) if((p[j].fenzi*p[j+1].fenmu)>(p[j+1].fenzi*p[j].fenmu)) { h=p[j];p[j]=p[j+1];p[j+1]=h; } printf("n=%dnThe %d Item=%d/%dn",n,k,p[k].fenzi,p[k].fenmu);}