第26题-循环位数

本文包含欧拉项目第26题的解法

问题描述

第26题图

这个问题翻译为中文就是：

单位分数指分子为1的分数，如下是一些单位分数的小数表示， $1/6$ 的小数表示无限循环部分长度为1， $1/7$ 的小数表示无限循环部分长度是6

求解：找到小于1000的，单位分数无限循环部分最长的正整数d

解题思路

题目思维难度不大，把分数转小数小学就会做，列竖式求解就行，不过本题不是要让我们真的算出对应的小数来，只要找到无限循环部分长度就行。只要当前运算步骤的余数和之前计算结果重复了就说明会无限循环

rust语言实现

p26.rs

pub fn longest_cycle(n: usize) -> usize {
    let mut longest_cyc_num = 0;
    let mut lognest_cyc = 0;
    for i in 1..n {
        let rc = get_rec_cycle(i);
        if rc >= lognest_cyc {
            lognest_cyc = rc;
            longest_cyc_num = i;
        }
    }
    longest_cyc_num
}


pub fn get_rec_cycle(q: usize) -> usize {
    let mut p = 1;
    let mut pa: Vec<usize> = vec![];
    loop {
        let m = p % q;
        if m == 0 {
            return 0;
        }
        p = m * 10;
        if pa.contains(&m) {
            let index = pa.iter().position(|&r| r == m).unwrap();
            return pa.len() - index;
        }
        pa.push(m);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_longest_cycle() {
        assert_eq!(7, longest_cycle(10));
        assert_eq!(983, longest_cycle(1000));
    }

    #[test]
    fn test_get_rec_cycle() {
        assert_eq!(6, get_rec_cycle(7));
        assert_eq!(1, get_rec_cycle(3));
        assert_eq!(1, get_rec_cycle(6));
        assert_eq!(1, get_rec_cycle(9));
        assert_eq!(0, get_rec_cycle(5));
        assert_eq!(2, get_rec_cycle(11));
        assert_eq!(0, get_rec_cycle(10));
        assert_eq!(982, get_rec_cycle(983));
    }
}

代码解释

核心部分是求给定正整数，对应单位分数小数表示无限循环长度，在 get_rec_cycle 这个方法中，如果不是无限循环，那么必然返回0，维护了一个数组，用来保存每次除法运算得到的余数，当新的余数重复出现时就说明出现无限循环了。后面分别是单测和功能测试

本题可以用费马小定理验证，即对于任意的正整数p（不包括2、5）， 10^a 模p余1，这个a就是无限循环部位长度

用python验证

因为rust默认情况下没法做任意精度计算，所以拿python验证了一下，10的982次方确实模983余1