#include <iostream> typedef long long ll; using namespace std; ll FN(ll x) { ll a = x; for (ll i = 2; i * i <= x; i++) { if (x % i == 0) { a = a / i * (i - 1); while (x % i == 0) { x /= i; } } } if (x > 0) { a = a / x * (x - 1); } return a; } ll fp(ll a, ll b, ll p) { __int128 an = 1; for (a %= p; b; a = (__int128)a * a % p, b >>= 1) { if (b & 1) { an = (__int128)an * a % p; } } return an; } ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } int main() { ll p, q; cin >> p >> q; q /= gcd(p, q); ll s2 = 0, s5 = 0; while (q % 2 == 0) { s2++; q /= 2; } while (q % 5 == 0) { s5++; q /= 5; } if (q == 1) { cout << -1 << endl; } else { ll e = FN(q); ll mi = 1e18; for (ll i = 1; i * i <= e; i++) { if (e % i == 0) { if (fp(10, i, q) == 1) { mi = min(mi, i); } if (fp(10, e / i, q) == 1) { mi = min(mi, e / i); } } } cout << max(s2, s5) << " " << mi << endl; } return 0; }
解决一个数论问题，其目的是确定一个分数 p/q（其中 p 和 q 是输入的正整数且已约简过）的小数表示中循环节的长度。首先，代码分为几个主要函数：
FN(ll x)函数： 这个函数计算一个整数x的欧拉函数 ，即小于等于x且与x互质的正整数个数。通过分解质因数并应用欧拉定理的性质计算得出。fp(ll a, ll b, ll p)函数： 这是一个快速幂函数，计算a的b次方对p取模的结果，利用二进制快速幂算法实现，提高计算效率。gcd(ll a, ll b)函数： 计算两个整数的最大公约数，采用辗转相除法（欧几里得算法）。main()函数： 主函数接收输入的分数分子p和分母q，首先通过约简使得q不含质因子 2 和 5 的多余幂次（不影响循环节长度）。然后分别计算q中质因数 2 和 5 的指数（记作s2和s5），初步判断循环节长度至少为两者较大者。
接下来计算q的欧拉函数\phi(q)，并通过快速幂函数fp()查找使10的某个幂次对q取模等于1的最小指数，即10^mi ≡ 1 (mod q)，这个指数mi就是循环节的长度。这是因为10^mi代表的是循环节的周期。
输出循环节长度的最大可能值（max(s2, s5)）和通过搜索得到的mi，两者中较大的那个作为最终答案。如果q不含有除了 2 和 5 以外的质因数，则输出-1，表示分数p/q是有限小数。- 在C++编程中，
\_\_int128是一种特定编译器支持的128位整数类型。这意味着它可以存储一个128位（16字节）的整数值，比常规的int、long和long long类型所能表示的范围更大。
在这段代码中，
__int128 an = 1;
- 这条语句初始化了一个名为
an的128位整数变量，并将其设置为1。由于后面代码涉及到大数的计算（快速幂算法），使用__int128是为了能够容纳更大的中间计算结果，确保计算过程不会发生溢出。在这个上下文中，an被用作累乘的结果，随着循环的进行，它的值会不断增大，直到达到最终的幂次结果。
