//////////////////////////////////////////////////////////////////////////
/*
* 
* 
*
* 文件名稱：循環(huán)小數(shù).cpp
* 作 者：郭運(yùn)凱
* 完成日期：2008.09.23
* 此版本采用純理論計算，當(dāng)循環(huán)節(jié)長度大于 9后，會出現(xiàn)計算錯誤
 
*/////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <vector>
using namespace  std;

int zhengshu;//整數(shù)部分
int yushu;

 typedef struct node 
 {
	 int data;
	 int count;
	 struct node *lchild;
	 struct node *rchild;
 }*STree,TreeNode;

 typedef struct cnode 
 {
	 int data;
	 int count;
 }Cnode;
 
 vector<Cnode> R; //存儲分解質(zhì)因式的結(jié)果

 STree tr = NULL;

 void insertTree(STree & root,int n)
 {
	 if (root == NULL)
	 {
		 TreeNode * temp = new TreeNode;
		 temp->data = n;
		 temp->count = 1;
		 temp->lchild = NULL;
		 temp->rchild = NULL;
		 root = temp;
	 }
	 else 
	 {
		 if (root->data == n)
		 {
			 root->count ++;
		 }
		 else if (root->data > n)
		 {
			 insertTree(root->rchild,n);
		 }
		 else
		 {
			 insertTree(root->lchild,n);
		 }
	 }
 }

 void inorder(STree const root)
 {
	 if (root != NULL)
	 {
		 inorder(root->lchild);
		 Cnode t;
		 t.data = root->data;
		 t.count = root->count;
		 R.push_back(t);
		 inorder(root->rchild);

	 }	 
	 else		 
	 {		
	   return;
	 }
 }

int findgcd(int m, int n)
{ //求最大公約數(shù) 
	if (m < n)
	{
		int t = m;
		m = n;
		n = t;
	}

	int temm = 0;
	while ( m % n != 0)
	{
		temm = m;
		m = n;
		n = temm % n;
	}
	return n;
}

void huajian(int & n,int & m)
{
	int gcd = findgcd(m,n);

	if (gcd == 0)
	{
		printf("gcd = 0 \n");
	}
	else
	{
		m /= gcd;
		n /= gcd;
	}	
}
 void fenjie(int m)
 {
	 int i = 2;
	 bool fc = false;
	 bool found = false;

	 while(true)    //永遠(yuǎn)循環(huán)
	 {
		 for ( ;i<=sqrt(m);i++)
			 if(m % i==0) //i肯定是質(zhì)數(shù),N肯定不是質(zhì)數(shù)
			 {
				 fc = true;
				 found =  true;
				// cout<<i<<"×";
				 insertTree(tr,i); //把分解結(jié)果存入到查找樹中
				 m = m/i;
				 break ;
			 }
			 
			 if(fc) 
			 {
				 fc = false;
				 continue;
			 }
			 
			 if(found)
			 {
				 //cout<<m<<endl;
				 insertTree(tr,m);
			 }
			 else
			 {
				// cout<<m<<"是個質(zhì)數(shù)，不能分解"<<endl;
				 insertTree(tr,m);				 
			 }
			  break;			
	 }
 }
 void check(int n,int m)
 {
	 vector< int> result;
	 
	 bool other = false;
	 int othervalue = 1 ;

	 int shang,yushu;

	 int max25 = 0;

	 printf("%d.",zhengshu);

	 for ( int i = 0;i < R.size();i++)
	 {
		 if (R[i].data == 2 || R[i].data == 5)
		 {
			 if (R[i].count > max25)
			 {
				 max25 = R[i].count;				 
			 }
		 }
		 else
		 {
			 other = true;	
			 for (int k = 0;k < R[i].count;k++)
			 {
				  othervalue *= R[i].data;	
			 }
			
		 }
	 }

	 if (max25 != 0 )
	 {
		 if (!other)
		 {
			 /*結(jié)論1，一個最簡分?jǐn)?shù)，如果分母中除了2 和5 以外，不含其它質(zhì)因
				 數(shù)，則這個分?jǐn)?shù)必化為有限小數(shù)且在這個有限小數(shù)中，小數(shù)部分的位數(shù)
					等于分母中含2，5 因數(shù)個數(shù)的最大數(shù)．*/
		//////////////////////////////////////////////////////////////////////////
	//	printf(" 1. 一個最簡分?jǐn)?shù) \n");
			 
		yushu = n;
		while (yushu != 0)
		{
			shang = (10*yushu)/m;
			result.push_back(shang);
			yushu = (10*yushu) % m;
		}
	
		for (int i = 0;i < result.size();i++)
		{
			printf("%d",result[i]);
		}	

		 }
		 else
		 { 
			 //混合小數(shù) 
			 /*結(jié)論3，一個最簡分?jǐn)?shù)的分母中，如果既有2，5 這樣的因數(shù)，又含
			 有2，5 以外的質(zhì)因數(shù)則這個分?jǐn)?shù)定能化成混循環(huán)小數(shù)，它的不循環(huán)部分
			 的數(shù)字個數(shù)等于分母因數(shù)中2，5 個數(shù)較多一個的個數(shù)，循環(huán)節(jié)的最小位
			 數(shù)等于分母中除2，5 以外因數(shù)積能整除的9 構(gòu)成數(shù)字中最小數(shù)中含9 的
			個數(shù)．*/
			 //////////////////////////////////////////////////////////////////////////
			 
			yushu = n;

			for (int i = 0;i < max25;i++)
			{
				shang = (10*yushu)/m;
				result.push_back(shang);
			    yushu = (10*yushu) % m;
			}

			//計算后面循環(huán)節(jié)的長度
			int len = 1;
			int k = 9;
			while (k % othervalue != 0)
			{
				len++;
				k = k*10 +9;
				if (len >= 1024)
				{
					printf("is too long,break\n");
					break;
				} 
			}
            //求循環(huán)節(jié)
			for (i = 0; i< len; i++)
			{
				shang = (10*yushu)/m;
				result.push_back(shang);
			    yushu = (10*yushu) % m;
			}
		
			for (i = 0;i < max25; i ++)
			{
				printf("%d",result[i]);
			}

			printf("(");
			for (; i < max25 + len;i++)
			{
			printf("%d",result[i]);
			}
			printf(")");
		 }
		
	 }//end max 25 != 0
	 else
	 { 
	 /*結(jié)論2，一個最簡分?jǐn)?shù)，如果分母中只能分解出2 和5 以外的質(zhì)因數(shù)，
	 則這個分?jǐn)?shù)必化成純循環(huán)小數(shù)，這個純循環(huán)小數(shù)的循環(huán)節(jié)的最少位數(shù)等
	于能被分母整除的、由9 構(gòu)成的數(shù)中最小數(shù)的9 的個數(shù)．		 */
		 //計算后面循環(huán)節(jié)的長度
		// printf("3. 純循環(huán)小數(shù) \n");
		 //printf("%d \n",othervalue);
		 int len = 1;
		 int k = 9;
		
		 while (k % othervalue != 0)
		 {
			 len++;
			 k = k*10 +9;
			 if (len >= 1024)
			 {
				 printf("is too long,break\n");
				 break;
			 }
		 }

		 yushu = n;
		 
		 for (int i = 0;i < len;i++)
		 {
			 shang = (10*yushu)/m;
			 result.push_back(shang);
			 yushu = (10*yushu) % m;
		}

		 printf("(");
		 for (i = 0 ; i < max25 + len;i++)
		 {
			 printf("%d",result[i]);
		 }
			printf(")");
	 }
	 printf("\n");	 

 }
 void distroy(STree & root)
 {
	 if (root != NULL)
	 {
		 distroy(root->lchild);
		 distroy(root->rchild);
		 delete root;
		 root = NULL;
	 }
	 else 
		 return;
 }

 void caculate( int n,int m)
 {
   zhengshu = n/m;
   yushu = n % m;
   if (yushu == 0)
   {
	   printf("%d\n",zhengshu);
   }
   else
   {
	   n = yushu;
	   if (R.size() != 0)
	   {
		   R.erase(R.begin(),R.end());
	   }
	   if (tr != NULL)
	   {
		   distroy(tr);
	   }
	   huajian(n,m);
	   
	   fenjie(m);
	   inorder(tr);
      check(n,m);

   }
 
 }

 void main()
 {
	 int n,m;
	 printf("input n,m \n");
	 scanf("%d%d",&n,&m);
	 while (m != 0)
	 {
	caculate(n,m);
	 printf("input n,m \n");
   scanf("%d%d",&n,&m);
	 }	
 }