uva202:循环小数(循环节+抽屉原理)

题意:

给出两个数n,m,0<=n,m<=3000,输出n/m的循环小数表示以及循环节长度。


思路:

设立一个r[]数组记录循环小数,u[]记录每次的count,用于标记,小数计算可用 r[i]=n*10/m;n=n*10%10 直到n为0或u[n]!=0(找到循环节)

涉及到两个知识点:n/m的余数在0~m-1之间;

    抽屉原理:循环次数最多不超过m+1次

具体见代码。


//求循环节
#include<cstdio>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define For(i,a,b) for(int i=a;i<=b;i++)
int r[],s[],u[];
int n,m; int main()
{
for(;scanf("%d %d",&n,&m)==;)
{
int nn=n,count=;
mem(r,);mem(u,);
r[count++]=n/m;
n%=m;
while(!u[n]&&n){
u[n]=count;
s[count]=n;
r[count++]=*n/m;
n=n*%m;
}
printf("%d/%d=%d.",nn,m,r[]);
for(int i=;i<count&&i<=;i++)
{
if(n&&s[i]==n) printf("(");//还要想想
printf("%d",r[i]);
}
if(!n) printf("(0");
if(count>) printf("...");
printf(")\n");
printf(" %d = number of digits in repeating cycle\n\n",!n?:count-u[n]);
}
return ;
}
上一篇:如何对ConnectionString进行加密解码?


下一篇:Leetcode 494 Target Sum 动态规划 背包+滚动数据