问题：

给定两个数a、b，找出a/b的循环节，并按照指定格式输出。比如a=1、b=3，则输出0.(3)，即用括号包含循环节。

 

解法：

USCAO 2.4.5中的题 Fractions to Decimals
有一个tricky的解法，用分母中2的因子个数减去分子中2的因子个数，同样用分母中5的因子个数减去分子中5的因子个数，去两者这两者个数的最大值，这个就是分数的非循环部分的长度，这样偏移后，后面就是循­环部分，直到重复。

算法如下：

#include  < iostream >

using   namespace  std; 
typedef  long   long  int64; 

int  colcount = 0 ;

int  numBeforeRepeat( int  n, int  d)
{
    int c2=0,c5=0;
    if(n==0) return 1;
    while(d%2==0){d/=2;c2++;}//dominator 中2的个数
    while(d%5==0){d/=5;c5++;}//dominator 中5的个数
    while(n%2==0){n/=2;c2--;}//can go to negative
    while(n%5==0){n/=5;c5--;}//can go to negative
    if(c2>c5) {
        if(c2>0) return c2;
        else return 0;
    } else {
        if(c5>0) return c5;
        else return 0;
    }
}

void  print( char  c)
{
    if(colcount==76) {
        cout<<endl;
        colcount=0;
    }
    cout<<c;
    colcount++;
}

void  print( int  n)
{
    if(n>=10) print(n/10);
    print((char)('0'+(n%10)));
}  

int  main()
{
    int n,d;
    cin>>n>>d;
    print(n/d);
    print('.');
    n=n%d;
    int m=numBeforeRepeat(n,d);
    for(int i=0;i<m;i++) {
        n*=10;
        print(n/d);
        n%=d;
    }
    int r=n;
    if(r!=0) {
        print('(');
        do {
            n*=10;
            print(n/d);
            n%=d;
        } while(n!=r);
        print(')');
    }
    cout<<endl;
    return 0;
}

 

 

转载于:https://www.cnblogs.com/clive/archive/2009/10/28/Circular_decimal_fraction_USCAO_2_4_5.html

 分数化小数

对于一个分数（不一定是最简形式），给出它的小树形式，如果小数有循环节的话，把循环节放在一对圆括号中.

例如，1/4 =0.25,1/3=0.3333写成0.(3)，1/7= 0.142857142857...写成0.(142857)。如果结果是一种整数xxx，则用xxx.0 等表示整数xxx。

输入包括一行，包括被空格分隔开的分子N和分母D（第一个是N，第二个是D）。

输出包括一行，为转换后的小数形式。

样例输入

45 56

样例输出

0.803(571428)

分析

模拟除法的计算过程

整数部分：a/b

小数部分：

①mod = a%b；

②小数 = （mod*10） / b；

③mod = （mod*10）%b；

循环②③步，当出现重复的余数的时候，也就是循环节出现了

其实这道题的标签是“数论”，推荐队友的博客

分数化小数 计蒜客(无限循环小数 循环节 欧拉函数 欧拉定理 十进制)

C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a%b==0)
    {
        printf("%d.0\n",a/b);
        return 0;
    }
    map<int,int> m;//标记余数
    vector<int>rem;//余数
    rem.clear();
    vector<int> v;//商数
    v.clear();
    int pos=-1;
    while(true){
        v.push_back(a/b);
        int x=a%b;//余数
        if(x==0)  break;
        if(m[x]) {//map缺省情况下为0
            pos=find(rem.begin(),rem.end(),x)-rem.begin();
            break;
        }
        rem.push_back(x);
        m[x]=1;
        a=x*10;
    }
    printf("%d.",v[0]);
    for(int i=1;i<v.size();i++){
        if(i==pos+1)
            printf("(");
        printf("%d",v[i]);
    }
    if(pos>=0)    printf(")");
    return 0;
}

Java

import java.util.List;

import java.util.ArrayList;

import java.util.Scanner;

import java.util.Map;

import java.util.HashMap;
public class Main {
	static void f(int a,int b) {
		ArrayList<Integer> rem=new ArrayList<Integer>();//余数
		ArrayList<Integer> v=new ArrayList<Integer>();//商数
		HashMap<Integer,Integer> m=new HashMap<Integer,Integer>();//标记余数
		
		int pos=-1;
		while(true) {
			v.add(a/b);//商数
			int x=a%b;//余数
			if(x==0)	break;
			if(m.containsKey(x)) {//判断余数是否存在
				pos=rem.indexOf(x);//查找重复余数所在的位置
				break;
			}
			m.put(x,1);//标记
			rem.add(x);//将余数添加到动态数组中
			a=x*10;
		}
		System.out.print(v.get(0)+".");
		for(int i=1;i<v.size();i++) {
			if(pos+1==i)
				System.out.print("(");
			System.out.print(v.get(i));
		}
		if(pos>=0)
			System.out.println(")");
	}
    public static void main(String[] args) {
		Scanner cin=new Scanner(System.in);
		int a=cin.nextInt();
		int b=cin.nextInt();
		if(a%b==0) {
			System.out.println(a/b+".0");
		}else {
			f(a,b);
		}
		cin.close();
	}
}