90 lines
3.6 KiB
C++
90 lines
3.6 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
// 常量定义：数组最大长度为110，满足k≤100的需求
|
||
const int N = 110;
|
||
|
||
// 全局变量声明
|
||
int k; // 存储用户输入的k值，表示需要计算后k位的循环节长度
|
||
int a[N]; // 存储原始整数n的后k位数字（倒序存储：a[0]为个位，a[1]为十位...）
|
||
int b[N]; // 工作数组，用于存储幂运算的中间结果
|
||
int d[N] = {1}; // 高精度数组，存储最终循环节长度（初始值为1，乘法单位元）
|
||
|
||
/**
|
||
* 高精度乘法函数：计算两个数的乘积并仅保留后K位
|
||
* @param a 乘数1（倒序存储的高精度数组）
|
||
* @param b 乘数2（倒序存储的高精度数组）
|
||
* @note 结果将直接覆盖存储在a数组中
|
||
*/
|
||
void mul(int a[], int b[]) {
|
||
int c[N] = {0}; // 临时数组，存储乘法中间结果
|
||
|
||
// 1. 执行乘法运算（仅计算后K位）
|
||
for (int i = 0; i < k; i++)
|
||
for (int j = 0; j < k; j++)
|
||
if (i + j < k) // 确保不超出K位范围
|
||
c[i + j] += a[i] * b[j];
|
||
|
||
// 2. 处理进位并更新结果到a数组
|
||
int t = 0; // 进位变量
|
||
for (int i = 0; i < k; i++) {
|
||
t += c[i]; // 累加当前位乘积和进位
|
||
a[i] = t % 10; // 取模10得到当前位值
|
||
t /= 10; // 更新进位
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
string s; // 存储输入的超大整数n（支持10^100量级）
|
||
cin >> s >> k; // 读取输入：n和k
|
||
|
||
// 1. 初始化原始数组a（倒序存储n的后K位）
|
||
for (int i = s.size() - 1; i >= 0; i--)
|
||
a[s.size() - 1 - i] = s[i] - '0';
|
||
|
||
// 2. 逐位计算循环节（从最后1位到第k位）
|
||
for (int i = 0; i < k; i++) {
|
||
int st[11] = {0}; // 数字出现标记数组（检测循环冲突）
|
||
memcpy(b, a, sizeof a); // 复制初始状态到工作数组b
|
||
|
||
int j; // 当前位的循环节长度
|
||
// 最多尝试10次（0-9共10个可能数字，超过则无循环）
|
||
for (j = 1; j <= 10; j++) {
|
||
mul(b, a); // 计算b = b * a（仅保留后K位）
|
||
|
||
// 检查当前位是否回到初始值（找到循环节）
|
||
if (b[i] == a[i]) break;
|
||
|
||
/*
|
||
### 举例说明：
|
||
假设计算过程中出现数字序列： 3 → 7 → 2 → 7
|
||
- 当第二次出现7时，由于尚未回到初始值3，触发此冲突检测
|
||
- 这表明序列陷入了局部循环（7→2→7），永远无法回到初始值
|
||
这个机制确保了算法能够正确识别无法形成有效循环节的情况，是解决问题的关键判断条件之一。
|
||
*/
|
||
// 检测到数字重复出现但未回到初始值（存在循环冲突，无解决方案）
|
||
if (st[b[i]]) {
|
||
puts("-1");
|
||
return 0;
|
||
}
|
||
st[b[i]] = 1; // 标记该数字已出现
|
||
}
|
||
|
||
// 3. 更新循环节长度（高精度乘法：d = d * j）
|
||
int c[N] = {j}; // 将j转换为高精度数组
|
||
mul(d, c); // 累乘当前位的循环节长度
|
||
|
||
// 4. 更新乘数a为n^j的后K位（固定已计算的低位循环）
|
||
memcpy(b, a, sizeof a); // 重置b为初始值
|
||
for (int q = 1; q < j; q++)
|
||
mul(b, a); // 计算a^j的后K位
|
||
memcpy(a, b, sizeof b); // 更新a为新的乘数
|
||
}
|
||
|
||
// 4. 输出结果（去除前导零）
|
||
int dl = k - 1;
|
||
while (dl >= 0 && d[dl] == 0) dl--; // 找到最高有效位
|
||
for (int i = dl; i >= 0; i--)
|
||
cout << d[i];
|
||
return 0;
|
||
} |