C/C++教程
【C/C++无聊练手（一）】从「计算1/N的循环节」到「计算M/N的循环节」的理论推导&代码实现
文章目录
- 理论分析
- C实现1/N
- C++实现M/N
- C++实现CalCycleDiv类
- 下集预告&下下集预告
- 额外篇：mathematica实现
理论分析
分析一个复杂的问题，我们通常考虑它的简单形式，然后推广到一般。我们考虑 1 / N 1/N 1/N 的循环节问题，最简单的方法就是令 N N N 为较小的数，然后观察规律，最终推广。因此，我们先考虑 1 / 7 1/7 1/7 ——
1 / 7 = 0. 1 ˙ 4 ˙ 2 ˙ 8 ˙ 5 ˙ 7 ˙ (1.1) 1/7=0.\dot{1}\dot{4}\dot{2}\dot{8}\dot{5}\dot{7} \tag{1.1} 1/7=0.1˙4˙2˙8˙5˙7˙(1.1)
考虑到乘以 10 10 10 相当于小数点右移一位，例如
10 / 7 = 1. 4 ˙ 2 ˙ 8 ˙ 5 ˙ 7 ˙ 1 ˙ (1.2) 10/7=1.\dot{4}\dot{2}\dot{8}\dot{5}\dot{7}\dot{1} \tag{1.2} 10/7=1.4˙2˙8˙5˙7˙1˙(1.2)
那么，乘以 1 0 6 10^6 106 相当于小数点右移 6 6 6 位，即
1 0 6 / 7 = 142857. 1 ˙ 4 ˙ 2 ˙ 8 ˙ 5 ˙ 7 ˙ (1.3) 10^6/7=142857.\dot{1}\dot{4}\dot{2}\dot{8}\dot{5}\dot{7} \tag{1.3} 106/7=142857.1˙4˙2˙8˙5˙7˙(1.3)
我们知道， 1 1 1 除以 7 7 7 的余数为 1 1 1 ，我们记为 1 ( m o d 7 ) ≡ 1 1\left( \mathrm{mod}\ 7 \right) \equiv 1 1(mod 7)≡1 。
而「 1 0 6 10^6 106 除以 7 7 7 的循环节」与「 1 1 1 除以 7 7 7 的循环节」都是 1 ˙ 4 ˙ 2 ˙ 8 ˙ 5 ˙ 7 ˙ \dot{1}\dot{4}\dot{2}\dot{8}\dot{5}\dot{7} 1˙4˙2˙8˙5˙7˙ ，所以 1 0 6 10^6 106 除以 7 7 7 的余数等于 1 1 1 除以 7 7 7 的余数，我们记为
1 0 6 ( m o d 7 ) ≡ 1 0 0 ( m o d 7 ) ≡ 1 (1.4) 10^6\left( \mathrm{mod}\ 7 \right) \equiv 10^0\left( \mathrm{mod}\ 7 \right) \equiv 1 \tag{1.4} 106(mod 7)≡100(mod 7)≡1(1.4)
实际上， 1 / 7 1/7 1/7 小数点后的 1 , 2 , 3 , 4 , 5 , 6 1,2,3,4,5,6 1,2,3,4,5,6 位恰好是循环节，而此处 1 0 6 ( m o d 7 ) ≡ 1 0 0 ( m o d 7 ) 10^6\left( \mathrm{mod}\ 7 \right) \equiv 10^0\left( \mathrm{mod}\ 7 \right) 106(mod 7)≡100(mod 7) ，那么这不禁让我们猜想——
定理1：如果 1 0 q ≡ 1 0 p ( m o d N ) 10^{q}\equiv10^{p}\left(\mathrm{mod}\ N\right) 10q≡10p(mod N) ，那么小数点后 ( p , q ] \left(p,\ q\right] (p, q] 必是 1 / N 1/N 1/N 的循环节
该结论此处我们不证，我们继续看下一个例子，来说明这个结论的正确性——
我们考虑 1 / 6 = 0.1 6 ˙ 1/6=0.1\dot{6} 1/6=0.16˙ ，其中——
{ 1 0 0 ( m o d 6 ) ≡ 1 1 0 1 ( m o d 6 ) ≡ 4 1 0 2 ( m o d 6 ) ≡ 4 (1.5) \begin{cases} 10^0\left( \mathrm{mod}\ 6 \right) \equiv 1\\ 10^1\left( \mathrm{mod}\ 6 \right) \equiv 4\\ 10^2\left( \mathrm{mod}\ 6 \right) \equiv 4\\ \tag{1.5} \end{cases} ⎩⎪⎨⎪⎧100(mod 6)≡1101(mod 6)≡4102(mod 6)≡4(1.5)
对比定理1，此处 p = 1 , q = 2 p=1,q=2 p=1,q=2 ，所以小数点后第 ( p , q ] = 2 \left(p,\ q\right]=2 (p, q]=2 位就是循环节。
虽然定理1看起来只是一个充分条件，但它其实是充要的，这里也不予证明。此时，我们计算循环节的问题就归结为了计算 1 0 p ( m o d N ) 10^{p}\left(\mathrm{mod}\ N\right) 10p(mod N) ，如果遇到有相同的元素，那么就对应地区间就是循环节了。
不过我们自然还有一个问题—— p p p 的需要无穷无尽地算下去吗？答案是：没必要，循环节长度最大为 N − 1 N-1 N−1 。因为任何一个数 m o d N \mathrm{mod}\ N mod N 的取值范围都在 0 , 1 , ⋯ , N − 1 0,\ 1,\cdots,\ N-1 0, 1,⋯, N−1 里。特别地，如果遇到了 0 0 0 ，这代表 1 0 p 10^p 10p 可以整除 N N N ，那么这个数是一个有限小数。因此，循环小数不可能出现取值为 0 0 0 的情况，只要余数在 1 , ⋯ , N − 1 1,\cdots,\ N-1 1,⋯, N−1 出现了 2 2 2 次，那么这个区间就被确定下来了。根据抽屉原理，循环节长度最大为 N − 1 N-1 N−1 。因此，我们得到定理2——
定理2：如果 1 / N 1/N 1/N 不是一个有限小数，那么一定存在两个不同的非负整数 p , q ( p ≠ q ) p,q\left( p\neq q\right) p,q(p=q) ，其中 p < N , q < N p<N, \ q<N p<N, q<N ，使得 1 0 p ≡ 1 0 q ( m o d N ) 10^p\equiv 10^q\left(\mathrm{mod}\ N\right) 10p≡10q(mod N)
同样地，定理2我们也不证（事实上，证明的思想就是上面的抽屉原理）。根据这两个定理，我们就能确定 1 / N 1/N 1/N 的循环节问题计算思路了——
- 从
p
=
0
p=0
p=0 到
N
−
1
N-1
N−1 ，计算
1
0
p
(
m
o
d
N
)
10^p \left( \mathrm{mod}\ N\right)
10p(mod N)
- 如果当前 p = p 1 p=p_1 p=p1 与上面的某次 p = p 0 p=p_0 p=p0 的结果相同，那么循环节为 ( p 0 , p 1 ] \left(p_0,\ p_1\right] (p0, p1]
- 如果 1 0 p ( m o d N ) ≡ 0 10^p \left( \mathrm{mod}\ N\right)\equiv 0 10p(mod N)≡0 ，则该数是有限小数
当然，上面仅仅是一个思路，我们不会傻乎乎地 1 0 p ( m o d N ) 10^p \left( \mathrm{mod}\ N\right) 10p(mod N) ，我们实际上会通过递推的方式实现。
C实现1/N
代码如下——
#include <stdio.h>
#include <malloc.h>
void CalCycleDiv (int N) {
typedef unsigned char uint8; // 使用uint8表示0~9的数字，用以节省空间
if (N <= 0) { // 异常处理
printf("要求输入的N为正整数，您输入的N=%d\n", N);
return;
}
int remainder = 1; // 初始余数(10^0 mod N) == 1
uint8 *decimal = (uint8 *)malloc(N * sizeof(uint8)); // 小数部分
int *power = (int *)malloc(N * sizeof(int)); // power[10^p mod N] == p
int len = 0; // 当前小数位数
int loopP = 0; // 循环节范围(loopP, loopQ]
int loopQ = 0; // 循环节范围(loopP, loopQ]
for (int i = 0;i < N;++i) { // 初始化power为无效值N
power[i] = N;
}
while (true) {
decimal[len] = (uint8)(remainder / N); // 求商数
remainder = remainder % N; // 求余数
if (remainder == 0) { // 如果除尽了，必为有限小数
loopP = loopQ = len;
break;
}
if (power[remainder] != N) { // 如果10^(len) == 10^(power[remainder]) (mod N)
loopP = power[remainder];
loopQ = len;
break;
}
power[remainder] = len; // 记录10^(len) mod N == remainder
++len;
remainder *= 10;
}
// 显示输出
printf("%d / %d == %d.", 1, N, 1/N); // 整数部分
if (N == 1) { // 特殊处理N == 1
printf("0");
}
else{ // 非循环小数部分
for (int i = 1;i <= loopP;++i) {
printf("%d", decimal[i]);
}
}
if (loopP != loopQ) { // 循环小数部分
printf("[");
for (int i=loopP + 1;i <= loopQ;++i) {
printf("%d", decimal[i]);
}
printf("]");
}
printf("\n");
}
int main() {
for (int i = 0;i <= 13;++i) { // print [0, 13]
CalCycleDiv(i);
}
return 0;
}
输出结果——
要求输入的N为正整数，您输入的N=0 1 / 1 == 1.0 1 / 2 == 0.5 1 / 3 == 0.[3] 1 / 4 == 0.25 1 / 5 == 0.2 1 / 6 == 0.1[6] 1 / 7 == 0.[142857] 1 / 8 == 0.125 1 / 9 == 0.[1] 1 / 10 == 0.1 1 / 11 == 0.[09] 1 / 12 == 0.08[3] 1 / 13 == 0.[076923]
当然，你可以把输入参数调得更大，比如输入 CalCycleDiv(100003); ，输出的结果将会长得恐怖，光显示都花了我电脑1秒，复制到CSDN上直接卡了3秒。有兴趣的小伙伴可以自行尝试。
C++实现M/N
1
/
N
1/N
1/N 当然很好实现，而上述计算流程推广到
M
/
N
M/N
M/N 上并不困难。C++相对于C语言，引入了函数的多态，这就让我们可以很方便地实现 M/N 和 1/N 的函数重载。此时，我们如果只输入一个参数，就代表计算
1
/
N
1/N
1/N ，输入
2
2
2 个参数则代表计算
M
/
N
M/N
M/N 。其中我还顺便支持了
M
M
M 为负数、
0
0
0 ，
N
N
N 为负数的情形。
#include <iostream>
void CalCycleDiv (int N, int M=1) {
typedef unsigned char uint8; // 使用uint8表示0~9的数字，用以节省空间
if (N == 0) { // 异常处理
std::cout << "要求分母N不为0，您输入的N=" << N << std::endl;
return;
}
bool isNegative = false; // 如果是负数，那么输入加一个负号
int tmpN = N; // 用于显示输出
int tmpM = M; // 用于显示输出
if ((M < 0 && N > 0) || (M > 0 && N < 0))
isNegative = true;
M = (M > 0) ? M : (-M);
N = (N > 0) ? N : (-N);
int remainder = (M % N); // 初始余数(10^0 mod N) == 1
uint8 *decimal = new uint8[N]; // 小数部分
int *power = new int[N]; // power[10^p mod N] == p
int len = 0; // 当前小数位数
int loopP = 0; // 循环节范围(loopP, loopQ]
int loopQ = 0; // 循环节范围(loopP, loopQ]
for (int i = 0;i < N;++i) // 初始化power为无效值N
power[i] = N;
while (true) {
decimal[len] = (uint8)(remainder / N); // 求商数
remainder = remainder % N; // 求余数
if (remainder == 0) { // 如果除尽了，必为有限小数
loopP = loopQ = len;
break;
}
if (power[remainder] != N) { // 如果10^(len) == 10^(power[remainder]) (mod N)
loopP = power[remainder];
loopQ = len;
break;
}
power[remainder] = len; // 记录10^(len) mod N == remainder
++len;
remainder *= 10;
}
// 显示输出
std::cout << tmpM << " / " << tmpN << " == ";
if (isNegative)
std::cout << "-";
std::cout << M/N << "."; // 整数部分
if (N == 1 || M == 0) // 特殊处理N == 1
std::cout << "0";
else{ // 非循环小数部分
for (int i = 1;i <= loopP;++i)
std::cout << (int) decimal[i];
}
if (loopP != loopQ) { // 循环小数部分
std::cout << "[";
for (int i=loopP + 1;i <= loopQ;++i)
std::cout << (int) decimal[i];
std::cout << "]";
}
std::cout << std::endl;
delete(decimal); // 释放空间
delete(power);
}
int main() {
CalCycleDiv(13);
CalCycleDiv(-7, -3);
CalCycleDiv(7, -1);
CalCycleDiv(-7, 2);
return 0;
}
输出结果——
1 / 13 == 0.[076923] -3 / -7 == 0.[428571] -1 / 7 == -0.[142857] 2 / -7 == -0.[285714]
C++实现CalCycleDiv类
上面的代码比较丑陋，原因是——明明这个问题可以面向对象的
- 比如将显示和计算部分分离开；
- 比如执行完函数后，我想要查看循环节长度等信息，是不是可以通过面向对象的方式暴露出一些接口；
- 比如上面的函数执行完后，结果将会被销毁，通过面向对象，我们可以更方便地查看结果的内部信息。
使用C++的 class ，我们就能很方便地实现面向对象地对代码进行编程了。我们定义一个 CalCycleDiv 类，用于计算循环除法。
#include <iostream>
class CalCycleDiv{
public:
typedef unsigned char uint8; // 使用uint8表示0~9的数字，用以节省空间
CalCycleDiv(int N, int M=1); // 构造对象，并执行计算
void displayAsCyclicDecimal(); // 显示该分数的循环小数形式
void displayAllCyclicDecimal(); // 显示分子+分母+该分数的循环小数形式
void displayLoop(); // 单独显示循环节
int getM(); // 返回m_M
int getN(); // 返回m_N
int getP(); // 返回m_loopP
int getQ(); // 返回m_loopQ
int getLoopLength(); // 返回(m_loopQ - m_loopP)，即循环节长度
private:
int m_N; // N
int m_M; // M
bool m_isNegative; // 如果是负数，那么显示时加一个负号
uint8 *m_decimal; // 小数部分
int m_loopP; // 循环节范围(m_loopP, m_loopQ]
int m_loopQ;
};
CalCycleDiv::CalCycleDiv (int N, int M)
: m_N (N) // m_N = N; m_M = M;
, m_M (M) {
try {
if (N == 0) // 异常处理
throw -1;
}
catch (int errNum) {
std::cout << "CalCycleDiv的分母N为0，错误！" << std::endl;
}
// 如果是负数，那么输入加一个负号
if ((M < 0 && N > 0) || (M > 0 && N < 0))
m_isNegative = true;
else
m_isNegative = false;
M = (M > 0) ? M : (-M);
N = (N > 0) ? N : (-N);
// 正式开始计算
int remainder = (M % N); // 初始余数(10^0 mod N) == 1
m_decimal = new uint8[N]; // 小数部分
int *power = new int[N]; // power[10^p mod N] == p
int len = 0; // 当前小数位数
m_loopP = 0;
m_loopQ = 0;
for (int i = 0;i < N;++i) // 初始化power为无效值N
power[i] = N;
//std::cout << remainder << " " << len << " " << m_isNegative << " " << M << " " << N << std::endl;
while (true) {
m_decimal[len] = (uint8)(remainder / N); // 求商数
remainder = remainder % N; // 求余数
if (remainder == 0) { // 如果除尽了，必为有限小数
m_loopP = m_loopQ = len;
break;
}
if (power[remainder] != N) { // 如果10^(len) == 10^(power[remainder]) (mod N)
m_loopP = power[remainder];
m_loopQ = len;
break;
}
power[remainder] = len; // 记录10^(len) mod N == remainder
++len;
remainder *= 10;
}
delete(power); // 释放空间
}
// 显示该分数的循环小数形式
void CalCycleDiv::displayAsCyclicDecimal () {
if (m_isNegative) // 负号显示
std::cout << "-";
std::cout << m_M/m_N << "."; // 整数部分
if (m_N == 1 || m_M == 0) // 特殊处理N == 1或者M == 0
std::cout << "0";
else{ // 非循环小数部分
for (int i = 1;i <= m_loopP;++i)
std::cout << (int) m_decimal[i];
}
if (m_loopP != m_loopQ) { // 循环小数部分
std::cout << "[";
for (int i = m_loopP + 1;i <= m_loopQ;++i)
std::cout << (int) m_decimal[i];
std::cout << "]";
}
std::cout << std::endl;
}
// 显示该分数的循环小数形式
void CalCycleDiv::displayAllCyclicDecimal () {
std::cout << m_M << " / " << m_N << " == ";
CalCycleDiv:displayAsCyclicDecimal();
}
// 单独显示循环节
void CalCycleDiv::displayLoop () {
std::cout << "[";
if (m_loopP == m_loopQ) // 如果不循环就显示0
std::cout << "0" << std::endl;
else {
for (int i = m_loopP + 1;i <= m_loopQ;++i)
std::cout << (int) m_decimal[i];
}
std::cout << "]" << std::endl;
}
int CalCycleDiv::getM () {
return m_M;
}
int CalCycleDiv::getN () {
return m_N;
}
// 返回m_loopP
int CalCycleDiv::getP () {
return m_loopP;
}
// 返回m_loopQ
int CalCycleDiv::getQ () {
return m_loopQ;
}
// 返回(m_loopQ - m_loopP)，即循环节长度
int CalCycleDiv::getLoopLength () {
return m_loopQ - m_loopP;
}
int main() {
CalCycleDiv cyc1(13);
CalCycleDiv cyc2(-7, -3);
CalCycleDiv cyc3(7, -1);
CalCycleDiv cyc4(7, -1);
CalCycleDiv cyc5(-7, 2);
CalCycleDiv cyc6(100003);
CalCycleDiv cyc7(10000003);
CalCycleDiv cyc8(100000003);
cyc1.displayAllCyclicDecimal();
cyc2.displayAllCyclicDecimal();
cyc3.displayAllCyclicDecimal();
cyc4.displayAllCyclicDecimal();
cyc5.displayAllCyclicDecimal();
std::cout << cyc5.getM() << " / " << cyc5.getN() << "的循环节长度为" << cyc5.getLoopLength() << std::endl;
std::cout << cyc6.getM() << " / " << cyc6.getN() << "的循环节长度为" << cyc6.getLoopLength() << std::endl;
std::cout << cyc7.getM() << " / " << cyc7.getN() << "的循环节长度为" << cyc7.getLoopLength() << std::endl;
std::cout << cyc8.getM() << " / " << cyc8.getN() << "的循环节长度为" << cyc8.getLoopLength() << std::endl;
return 0;
}
输出代码——
1 / 13 == 0.[076923] -3 / -7 == 0.[428571] -1 / 7 == -0.[142857] -1 / 7 == -0.[142857] 2 / -7 == -0.[285714] 2 / -7的循环节长度为6 1 / 100003的循环节长度为50001 1 / 10000003的循环节长度为769230 1 / 100000003的循环节长度为693360
好家伙，我们的代码直接可以计算出千万级别输入（10000003）的除法循环节长度。至于为啥我们不显示出来？当然是因为这里的空白太小了，写不下啦(x)
下集预告&下下集预告
对于这个代码，其实我们还不够满意。因为只能计算千万级别的输入显然不够coooooool！我们希望挑战一个高难度任务，让我们能计算 1000000007 这种十亿级别的输入。不过我们会遇到一大困难——结果的长度有 1000000006 位，而我们代码的空间复杂度近似于
5
N
5N
5N ，常数
5
5
5 十分大。这使得我们在计算 1000000007 这种十亿级别的输入时，内存会被直接吃完。
下下篇文章中，我们将通过近世代数的理论，将代码的空间复杂度优化到 N N N （事实上，可以优化到 N / 2 N/2 N/2 ，不过这样写起来麻烦些）。为了实现这样的优化，我们需要编写一个质因数分解的类，作为中间的辅助类，而这将放到下篇文章中进行。
额外篇：mathematica实现
mathematica：花里胡哨！我只需要一行代码
RealDigits[1/7][[1]]
输出
{{1, 4, 2, 8, 5, 7}}
天啊！ m a t h e m a t i c a Y Y D S \mathrm{mathematica}\ \mathscr{Y}\mathcal{Y}\mathscr{D}\mathcal{S} mathematica YYDS ！
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
