#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/************************************************************************
*功能：返回 1/n 的重复周期 和 1/n的商 （可选）
*说明：模拟了实际的 1/n 的计算过程，除数始终为n,被除数初始为1,numerator = 1，商集合fraction为空，余数集合reminder为空
执行下面的循环：
1. 如果numerator < n，不够除，则numerator *= 10,同时0追加到fraction中，如此循环，直到够除，才跳转到2
2. 计算余数c = numerator % n,并将商numerator/n 追加都fraction中，如果c==0，则表示能除尽，不存在重复周期，返回0和fraction，跳转到4。否则跳转到3
3. 余数c != 0, 查找reminder,确定c是否出现过，如果出现过，则出现了重复周期，则统计第一次出现（包括这次）直到reminder结束的数字个数cnt。返回cnt和fraction，跳转到4.否则将余数c追加到reminder中，c 赋给numerator,numerator = c,跳转到1，继续循环。
4. 结束
************************************************************************/
int div(int n)
{
    int numerator = 1; // 被除数（分子）
    vector<int> fraction; // 商 集合 (如果需要，可以返回这个商)
    vector<int> reminder; // 余数 集合

    while (1){

        // Step 1 : 确保numerator >= n
        while (numerator < n){
            numerator *= 10;
            fraction.push_back(0);
        }

        // Step 2 ：计算余数c
        int c = numerator % n;
        fraction.push_back(numerator/n);
        //cout<<"c:"<<c<<endl;
        if (c == 0){
            return 0; // 能除尽，结束
        }

        // Step 3 ：余数不为0，判断余数是否出现过
        else{
            // 找到c出现的位置
            vector<int>::iterator it = find(reminder.begin(), reminder.end(), c);
            if (it != reminder.end()){ // 出现过，说明有重复了
                int cnt=0;
                for (; it!=reminder.end(); ++it ){ // 从上次出现的位置，计算到当前的长度
                    cnt++;
                }
                return cnt;
            }
            else{ //没出现过
                reminder.push_back(c);
                numerator = c; // 继续下一轮
            }
        }
    }
}

int main()
{
    int max_index = 0, max_cycle = 0;
    for (int i=1; i<1000; i++){
        if (div(i) > max_cycle){
            max_index = i;
            max_cycle = div(i);
        }
    }
    cout<<"重复周期最长的数为："<<max_index<<endl;
    cout<<"最长的重复周期为： "<<max_cycle<<endl;
    return 0;
}

package main

import "fmt"

/************************************************************************
*功能：返回 1/n 的重复周期 和 1/n的商 （可选）
*说明：模拟了实际的 1/n 的计算过程，除数始终为n,被除数初始为1,numerator = 1，商集合fraction为空，余数集合reminder为空
执行下面的循环：
1. 如果numerator < n，不够除，则numerator *= 10,同时0追加到fraction中，如此循环，直到够除，才跳转到2
2. 计算余数c = numerator % n,并将商numerator/n 追加都fraction中，如果c==0，则表示能除尽，不存在重复周期，返回0和fraction，跳转到4。否则跳转到3
3. 余数c != 0, 查找reminder,确定c是否出现过，如果出现过，则出现了重复周期，则统计第一次出现（包括这次）直到reminder结束的数字个数cnt。返回cnt和fraction，跳转到4.否则将余数c追加到reminder中，c 赋给numerator,numerator = c,跳转到1，继续循环。
4. 结束
************************************************************************/
func div(n int) int {

	numerator := 1             // 被除数（分子）
	fraction := make([]int, 0) // 商 集合 (如果需要，可以返回这个商)
	reminder := make([]int, 0) // 余数 集合

	for {

		// Step 1 : 确保 numerator >= n
		for numerator < n {
			numerator *= 10
			fraction = append(fraction, 0)
		}

		// Step 2 ：计算余数c
		c := numerator % n
		fraction = append(fraction, numerator/n)
		if c == 0 {
			return 0 // 能除尽，结束
		}

		// Step 3 ：余数不为0，判断余数c是否出现过
		loc := -1
		for i, r := range reminder {
			if r == c {
				loc = i
				break
			}
		}

		if loc >= 0 { // 出现过，说明有重复了
			size := len(reminder) - loc // 从上次出现的位置，计算到当前的长度
			return size
		} else { // 没有出现过，继续往后除
			reminder = append(reminder, c)
			numerator = c
		}
	}

	return 0
}

func main() {
	maxIndex, maxCycle := 0, 0
	for i := 1; i < 1000; i++ {
		if div(i) > maxCycle {
			maxIndex = i
			maxCycle = div(i)
		}
	}

	fmt.Println("重复周期最长的数为：", maxIndex)
	fmt.Println("最长的重复周期为：", maxCycle)
}

#************************************************************************
#功能：返回 1/n 的重复周期 和 1/n的商 （可选）
#说明：模拟了实际的 1/n 的计算过程，除数始终为n,被除数初始为1,numerator = 1，商集合fraction为空，余数集合reminder为空
#执行下面的循环：
# 1. 如果numerator < n，不够除，则numerator *= 10,同时0追加到fraction中，如此循环，直到够除，才跳转到2
# 2. 计算余数c = numerator % n,并将商numerator/n 追加都fraction中，如果c==0，则表示能除尽，不存在重复周期，返回0和fraction，跳转到4。否则跳转到3
# 3. 余数c != 0, 查找reminder,确定c是否出现过，如果出现过，则出现了重复周期，则统计第一次出现（包括这次）直到reminder结束的数字个数cnt。返回cnt和fraction，跳转到4.否则将余数c追加到reminder中，c 赋给numerator,numerator = c,跳转到1，继续循环。
# 4. 结束
#************************************************************************
def div(n) :

	numerator = 1 # 被除数（分子）
	fraction = [] # 商 集合 (如果需要，可以返回这个商)
	reminder = [] # 余数 集合

	while True:

		# Step 1 : 确保 numerator >= n
		while numerator < n :
			numerator *= 10
			fraction.append(0)

		# Step 2 ：计算余数c
		c = numerator % n
		fraction.append(numerator/n)
		if c == 0 :
			return 0 # 能除尽，结束

		# Step 3 ：余数不为0，判断余数c是否出现过
		if c in reminder :
			# 出现过，说明有重复了
			for i, r in enumerate(reminder):
				if r == c :
					return len(reminder) - i # 从上次出现的位置，计算到当前的长度

		# 没有出现过，继续往后除
		reminder.append(c)
		numerator = c


maxIndex, maxCycle = 0, 0
for i in range(1,1000) :
		if div(i) > maxCycle :
			maxIndex = i
			maxCycle = div(i)

print("重复周期最长的数为：", maxIndex)
print("最长的重复周期为：", maxCycle)

void ex26()
{
    int maxlen = 0, maxn = 0;

    for(int n = 2 ; n <= 1000 ; n++ ){
        int rest = 1;

        for(int i = 0 ; i < n ; i++ ) rest = (rest*10) % n; // code-1

        int r0 = rest; //code-2
        int len = 0;
        do { //code-3
            rest = (rest*10)%n;
            len++;
        } while( rest != r0 );

        if( len > maxlen ){ //code-4
            maxn = n;
            maxlen = len;
        }
    }

    printf("ex26: %d: %d\n", maxn, maxlen);
}