找到
1
篇与
gcd
相关的结果
-
![P1050 [NOIP 2005 普及组] 循环](//blog.xiaoeyv.com/usr/themes/joe/assets/images/lazyload.gif)
P1050 [NOIP 2005 普及组] 循环 题目解读 给定一个非常大的整数 $n$ 和一个小整数 $k$，要求计算 $n$ 的正整数次幂 $n^a$ 的 最后 $k$ 位 数字，且这些最后 $k$ 位数字是否会存在某种 循环规律。如果存在这样的循环规律，要求输出 最小的循环长度，如果没有循环规律，则输出 -1。 让我们来看样例 输入：n = 32, k = 2 输出：4 列个表格： $a$$32^a$$32^a \mod 10^2$1323221024243327686841048576765335544323261073741824247343597383686881099511627776769351843720888323210112589990684262424从表格中可以看到： 当 a=1 时，余数为 32。 当 a=2 时，余数为 24。 当 a=3 时，余数为 68。 当 a=4 时，余数为 76。 当 a=5 时，余数再次变为 32，与 a=1 时相同，开始循环。 此后余数序列重复：32 → 24 → 68 → 76 → 32 → ...，循环长度为 4。 知识铺垫 1. 快速幂 问题： 计算 $ n^a \mod 10^k $，如果 $ a $ 很大，直接乘 $ a $ 次会超慢。 快速幂的核心思想：把指数 $ a $ 拆成二进制（就像折纸一样，反复对折），用平方和乘法代替重复乘法。这样能把计算次数从 $ O(a) $ 降到 $ O(\log a) $。 证明 任何指数 $ a $ 可以转换为二进制，这相当于 $ a = 2^{k_1} + 2^{k_2} + \cdots $。 计算 $ n^a $ 时，因为乘法有分配律，我们可以将问题转化为 $ n^1 \times n^2 \times n^4 \times n^8 \times \ldots $。 2. 阶： 在模运算中，幂的结果会循环。阶就是这个循环的最小周期。以样例 $ 32 $ 为例，他的阶就是 $ 4 $。 具体运用 如果知道阶 $d$（循环周期），当 $n^{d} \equiv 1 \pmod{m}$ 时，我们可以构造以下式子： $$ \begin{aligned} n^{d+1} &\equiv n^d \cdot n \equiv 1 \cdot n \equiv n \pmod{m}, \\\\ n^{d+2} &\equiv n^d \cdot n^2 \equiv 1 \cdot n^2 \equiv n^2 \pmod{m}, \\\\ &\quad \vdots \\\\ n^{d+k} &\equiv n^k \pmod{m}. \end{aligned} $$ 由这个式子，我们可以得出 $ n^{a} \equiv n^{a \mod d} \pmod{m} $，将大指数 $ a $ 缩小到 $ a \mod d $。 找阶的方法 条件： $n$ 和模数 $m$ 必须互质，即最大公约数 $\gcd(n, m) = 1$。因为这道题中 $m = 10^k$，所以要求 $n$ 不能被 2 或 5 整除。 欧拉定理： 如果 $\gcd(n, m) = 1$，则 $n^{\phi(m)} \equiv 1 \pmod{m}$。$\phi(m)$ 是小于 $m$ 且与 $m$ 互质的数的个数。 欧拉函数 $\phi(n)$ 的定义： 对于正整数 $n$，欧拉函数 $\phi(n)$ 表示小于或等于 $n$ 的正整数中与 $n$ 互质的数的个数。如果 $n$ 有标准质因数分解： $$ n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} $$那么： $$ \phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right) $$ 应用于 $m = 10^k$： 首先对 $10^k$ 进行质因数分解： $$ 10^k = (2 \times 5)^k = 2^k \times 5^k. $$因此，$10^k$ 的质因数为 2 和 5。代入欧拉函数公式： $$ \phi(10^k) = 10^k \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right). $$所以： $$ \phi(10^k) = 10^k \times \frac{1}{2} \times \frac{4}{5} = 10^k \times \frac{2}{5}. $$进一步化简： $$ \phi(10^k) = \frac{2}{5} \times 10^k = 4 \times 10^{k-1}. $$ 所以对于 $ m = 10^k $，有 $ \phi(10^k) = 10^k \times (1 - \frac{1}{2}) \times (1 - \frac{1}{5}) = 4 \times 10^{k-1} $。 阶 $ d $ 的性质： $ d $ 是最小正整数，使得 $ n^d \equiv 1 \pmod{m} $，且 $ d $ 必须整除 $ \phi(m) $。这里就不证明了，感兴趣可以去自行学习。 找 $ d $ 的步骤： 计算 $ \phi(m) $（如 $ m = 10^k $，则 $ \phi(10^k) = 4 \times 10^{k-1} $。 列出 $ \phi(m) $ 的所有正除数（从小到大）。 测试最小的除数 $ d $ 满足 $ n^d \equiv 1 \pmod{m} $。 这里注意，由于本题的数据范围极大，第 iii 步需要用快速幂算。 For example 找 $ n = 3 $ 在 $ \mod 100 $（即 $ 10^2 $，$ k=2 $ 下的阶。 条件：$ \gcd(3, 100) = 1 $（互质），阶存在。 计算 $ \phi(100) = 100 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{5}) = 40 $。 $ \phi(100) = 40 $ 的除数：1, 2, 4, 5, 8, 10, 20, 40。 测试（用快速幂算 $ 3^d \mod 100 $： $ d = 1 $: $ 3^1 = 3 \not\equiv 1 $ $ d = 2 $: $ 3^2 = 9 \not\equiv 1 $ $ d = 4 $: $ 3^4 = 81 \not\equiv 1 $ $ d = 5 $: $ 3^5 = 243 \equiv 43 \not\equiv 1 $ $ d = 8 $: $ 3^8 = (3^4)^2 = 81^2 = 6561 \equiv 61 \not\equiv 1 $ $ d = 10 $: $ 3^{10} = (3^5)^2 = 243^2 \equiv 43^2 = 1849 \equiv 49 \not\equiv 1 $ $ d = 20 $: $ 3^{20} \equiv (3^{10})^2 \equiv 49^2 = 2401 \equiv 1 \pmod{100} $（成立！） 所以阶 $ d = 20 $。序列每 20 次幂循环一次（如 $ 3^1 \equiv 03 $, $ 3^2 \equiv 09 $, ..., $ 3^{20} \equiv 01 $, $ 3^{21} \equiv 03 $, ...）。 结合快速幂和阶计算 $ n^a \mod 10^k $ 情况 1：$ n $ 和 $ 10^k $ 互质（即 $ n $ 是奇数且不被 5 整除） 这里由于阶存在，我们可以减少指数大小。 步骤： 找阶 $ d $： 计算 $ \phi(10^k) = 4 \times 10^{k-1} $。 找最小 $ d $（整除 $ \phi(10^k) $ 使得 $ n^d \equiv 1 \pmod{10^k} $。 缩小指数：计算 $ r = a \mod d $。 计算结果：因为 $ n^a \equiv n^r \pmod{10^k} $，所以用快速幂计算 $ n^r \mod 10^k $ 就可以算出结果了。 For example 计算 $ 3^{100} \mod 100 $。 $ n = 3 $, $ k = 2 $, $ m = 100 $。 互质：是（$ \gcd(3, 100) = 1 $。 找阶：如前，$ d = 20 $。 缩小指数：$ r = 100 \mod 20 = 0 $（当 $ r = 0 $，取 $ n^d \equiv 1 $。 结果：$ 3^{100} \equiv 1 \pmod{100} $。 情况 2：$ n $ 和 $ 10^k $ 不互质（即 $ n $ 含因子 2 或 5） 这里由于欧拉定理要求互质，所以阶可能不存在。 处理思路： 对于大 $ a $，$ n^a \mod 10^k $ 可能最终为 0（如果 $ n $ 含 2 和 5），或进入一个“稳定循环”。但在实践中，常用以下方法： 分离因子：把 $ n $ 写成 $ n = 2^p \times 5^q \times m $，其中 $ m $ 与 10 互质。 计算 $ m^a \mod 10^k $：用情况 1 的方法（阶和快速幂）。 组合结果：结合因子 $ 2^{p a} $ 和 $ 5^{q a} $ 的影响（可能需额外处理）。 代码设计 大整数处理 由于 $n$ 可能非常大，我们使用字符串来表示 $n$，并通过字符串模拟大整数的加法、乘法和除法操作。 求解过程 计算模数：计算 $10^k$（即 $10^k$ 的值）并通过模运算得到结果。 逐步计算次幂：通过逐步计算 $n^a \mod 10^k$，记录每次出现的结果并检查是否出现了重复。 找最小循环长度：如果某个次幂的结果与之前的结果相同，那么就找到了循环，返回循环长度。 完整代码 #include <bits/stdc++.h> using namespace std; // 大整数以10^9为基数的高精度表示 const long long BASE = 1000000000; struct BigInt { vector<long long> a; // 低位块在前 BigInt() {} BigInt(long long v) { *this = v; } BigInt& operator=(long long v) { a.clear(); if (v > 0) { while (v) { a.push_back(v % BASE); v /= BASE; } } return *this; } }; void trim(BigInt &x) { while (!x.a.empty() && x.a.back() == 0) x.a.pop_back(); } bool isZero(const BigInt &x) { return x.a.empty(); } int cmpBig(const BigInt &x, const BigInt &y) { if (x.a.size() != y.a.size()) return x.a.size() < y.a.size() ? -1 : 1; for (int i = (int)x.a.size()-1; i >= 0; --i) { if (x.a[i] != y.a[i]) return x.a[i] < y.a[i] ? -1 : 1; } return 0; } // 大整数加法 BigInt addBig(const BigInt &x, const BigInt &y) { BigInt res; long long carry = 0; size_t n = max(x.a.size(), y.a.size()); res.a.resize(n); for (size_t i = 0; i < n; i++) { long long xi = (i < x.a.size() ? x.a[i] : 0); long long yi = (i < y.a.size() ? y.a[i] : 0); long long s = xi + yi + carry; res.a[i] = s % BASE; carry = s / BASE; } if (carry) res.a.push_back(carry); return res; } // 大整数减法（假设 x >= y） BigInt subBig(const BigInt &x, const BigInt &y) { BigInt res; long long carry = 0; size_t n = x.a.size(); res.a.resize(n); for (size_t i = 0; i < n; i++) { long long xi = x.a[i], yi = (i < y.a.size() ? y.a[i] : 0); long long s = xi - yi - carry; if (s < 0) { s += BASE; carry = 1; } else carry = 0; res.a[i] = s; } trim(res); return res; } // 大整数乘以小整数 BigInt mulSmall(const BigInt &x, long long m) { if (m == 0 || isZero(x)) return BigInt(0); BigInt res; __int128 carry = 0; res.a.resize(x.a.size()); for (size_t i = 0; i < x.a.size(); i++) { __int128 prod = (__int128)x.a[i] * m + carry; res.a[i] = (long long)(prod % BASE); carry = prod / BASE; } while (carry) { res.a.push_back((long long)(carry % BASE)); carry /= BASE; } return res; } // 大整数乘法 BigInt mulBig(const BigInt &x, const BigInt &y) { if (isZero(x) || isZero(y)) return BigInt(0); BigInt res; res.a.assign(x.a.size() + y.a.size(), 0); for (size_t i = 0; i < x.a.size(); i++) { __int128 carry = 0; for (size_t j = 0; j < y.a.size() || carry; j++) { __int128 cur = res.a[i+j] + (__int128)x.a[i] * (j < y.a.size() ? y.a[j] : 0) + carry; res.a[i+j] = (long long)(cur % BASE); carry = cur / BASE; } } trim(res); return res; } // 大整数除以小整数（结果向下取整） BigInt divSmall(const BigInt &x, int m) { BigInt res; res.a.resize(x.a.size()); __int128 carry = 0; for (int i = (int)x.a.size() - 1; i >= 0; i--) { __int128 cur = x.a[i] + carry * BASE; res.a[i] = (long long)(cur / m); carry = cur % m; } trim(res); return res; } // 大整数对小整数取模 int modSmall(const BigInt &x, int m) { __int128 rem = 0; for (int i = (int)x.a.size() - 1; i >= 0; i--) { rem = (rem * BASE + x.a[i]) % m; } return (int)rem; } // 大整数模运算：返回 a mod m BigInt modBig(const BigInt &a, const BigInt &m) { BigInt res = a; if (cmpBig(res, m) < 0) return res; int n = (int)res.a.size(); BigInt cur; cur.a.clear(); for (int i = n - 1; i >= 0; --i) { cur.a.insert(cur.a.begin(), res.a[i]); trim(cur); long long low = 0, high = BASE - 1, best = 0; while (low <= high) { long long mid = (low + high) >> 1; BigInt prod = mulSmall(m, mid); if (cmpBig(prod, cur) <= 0) { best = mid; low = mid + 1; } else { high = mid - 1; } } if (best) { BigInt tmp = mulSmall(m, best); cur = subBig(cur, tmp); } } trim(cur); return cur; } // 大整数欧几里得算法求 GCD BigInt gcdBig(BigInt a, BigInt b) { while (!isZero(b)) { BigInt r = modBig(a, b); a = b; b = r; } return a; } // 大整数快速幂（指数用大数十进制字符串） BigInt pow_mod_str(BigInt base, string exp, const BigInt &mod) { BigInt result(1); while (!(exp.size() == 1 && exp[0] == '0')) { int last = exp.back() - '0'; if (last % 2 == 1) { BigInt mul = mulBig(result, base); result = modBig(mul, mod); } BigInt sq = mulBig(base, base); base = modBig(sq, mod); // exp = exp / 2 int carry = 0; for (int i = 0; i < (int)exp.size(); i++) { int cur = carry * 10 + (exp[i] - '0'); exp[i] = (char)('0' + (cur / 2)); carry = cur % 2; } while (exp.size() > 1 && exp[0] == '0') exp.erase(exp.begin()); } return result; } // 将 BigInt 转为字符串 string toString(const BigInt &x) { if (x.a.empty()) return "0"; string s = to_string(x.a.back()); for (int i = (int)x.a.size()-2; i >= 0; i--) { char buf[16]; sprintf(buf, "%09lld", x.a[i]); s += buf; } return s; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); string n; int k; cin >> n >> k; // 统计 n 中因子 2 和 5 的幂次 int v2 = 0, v5 = 0; // 复制字符串来反复整除 string temp = n; // 计算 v2 while (true) { int carry = 0; string next; next.reserve(temp.size()); for (char c : temp) { int d = c - '0'; int val = carry * 10 + d; next.push_back(char('0' + (val / 2))); carry = val % 2; } if (carry != 0) break; // 不能整除 v2++; // 去除前导零 size_t pos = next.find_first_not_of('0'); if (pos == string::npos) { temp = "0"; break; } temp = next.substr(pos); } // 计算 v5 while (true) { int carry = 0; string next; next.reserve(temp.size()); for (char c : temp) { int d = c - '0'; int val = carry * 10 + d; next.push_back(char('0' + (val / 5))); carry = val % 5; } if (carry != 0) break; v5++; size_t pos = next.find_first_not_of('0'); if (pos == string::npos) { temp = "0"; break; } temp = next.substr(pos); } // 如果存在非平凡因子但小于 k，则无全局循环 if ((v2 > 0 && v2 < k) || (v5 > 0 && v5 < k)) { cout << -1; return 0; } // 如果同时 v2>=k 且 v5>=k，则所有幂的后 k 位都为 0，循环长度为 1 if (v2 >= k && v5 >= k) { cout << 1; return 0; } // 辅助函数：计算 n mod M auto mod_from_string = [&](const BigInt &M)->BigInt { BigInt res(0); for (char c : n) { res = mulSmall(res, 10); BigInt addv(c - '0'); res = addBig(res, addv); if (!isZero(res)) res = modBig(res, M); } return res; }; BigInt one(1), L2(1), L5(1); // 只需处理模 5^k 的情况（v2>=k） if (v2 >= k) { BigInt M5(1); for (int i = 0; i < k; i++) M5 = mulSmall(M5, 5); BigInt nmod = mod_from_string(M5); // 计算模 5^k 的阶：先用 φ(5^k)=4*5^(k-1) 逐步去因子 BigInt phi5(1); phi5 = mulSmall(phi5, 4); for (int i = 1; i < k; i++) phi5 = mulSmall(phi5, 5); L5 = phi5; // 尝试去掉因子 2 while (modSmall(L5, 2) == 0) { BigInt half = divSmall(L5, 2); string exp_str = toString(half); BigInt t = pow_mod_str(nmod, exp_str, M5); if (cmpBig(t, one) == 0) L5 = half; else break; } // 尝试去掉因子 5 while (modSmall(L5, 5) == 0) { BigInt fifth = divSmall(L5, 5); string exp_str = toString(fifth); BigInt t = pow_mod_str(nmod, exp_str, M5); if (cmpBig(t, one) == 0) L5 = fifth; else break; } cout << toString(L5); return 0; } // 只需处理模 2^k 的情况（v5>=k） if (v5 >= k) { BigInt M2(1); for (int i = 0; i < k; i++) M2 = mulSmall(M2, 2); BigInt nmod = mod_from_string(M2); BigInt phi2(1); for (int i = 0; i < k-1; i++) phi2 = mulSmall(phi2, 2); L2 = phi2; while (modSmall(L2, 2) == 0) { BigInt half = divSmall(L2, 2); string exp_str = toString(half); BigInt t = pow_mod_str(nmod, exp_str, M2); if (cmpBig(t, one) == 0) L2 = half; else break; } cout << toString(L2); return 0; } // v2=v5=0，需同时处理模 2^k 和模 5^k { BigInt M5(1); for (int i = 0; i < k; i++) M5 = mulSmall(M5, 5); BigInt nmod = mod_from_string(M5); BigInt phi5(1); phi5 = mulSmall(phi5, 4); for (int i = 1; i < k; i++) phi5 = mulSmall(phi5, 5); L5 = phi5; while (modSmall(L5, 2) == 0) { BigInt half = divSmall(L5, 2); string exp_str = toString(half); BigInt t = pow_mod_str(nmod, exp_str, M5); if (cmpBig(t, one) == 0) L5 = half; else break; } while (modSmall(L5, 5) == 0) { BigInt fifth = divSmall(L5, 5); string exp_str = toString(fifth); BigInt t = pow_mod_str(nmod, exp_str, M5); if (cmpBig(t, one) == 0) L5 = fifth; else break; } } { BigInt M2(1); for (int i = 0; i < k; i++) M2 = mulSmall(M2, 2); BigInt nmod = mod_from_string(M2); BigInt phi2(1); for (int i = 0; i < k-1; i++) phi2 = mulSmall(phi2, 2); L2 = phi2; while (modSmall(L2, 2) == 0) { BigInt half = divSmall(L2, 2); string exp_str = toString(half); BigInt t = pow_mod_str(nmod, exp_str, M2); if (cmpBig(t, one) == 0) L2 = half; else break; } } // 答案是 L = lcm(L2, L5) = (L2 / gcd(L2,L5)) * L5 BigInt g = gcdBig(L2, L5); BigInt quotient; { BigInt x = L2, d = g; int n = (int)x.a.size(); int m = (int)d.a.size(); quotient.a.assign(max(0, n - m + 1), 0); BigInt rem; rem.a.clear(); for (int i = n - 1; i >= 0; --i) { rem.a.insert(rem.a.begin(), x.a[i]); trim(rem); long long low = 0, high = BASE - 1, best = 0; while (low <= high) { long long mid = (low + high) >> 1; BigInt prod = mulSmall(d, mid); if (cmpBig(prod, rem) <= 0) { best = mid; low = mid + 1; } else { high = mid - 1; } } if (best) { BigInt tmp = mulSmall(d, best); rem = subBig(rem, tmp); } if (i - m + 1 >= 0) quotient.a[i - m + 1] = best; } trim(quotient); } BigInt L = mulBig(quotient, L5); cout << toString(L); return 0; }
![P1050 [NOIP 2005 普及组] 循环](http://blog.xiaoeyv.com/usr/themes/joe/assets/images/thumb/32.jpg)
