[ARC050C] LCM 111 题解

一句话题解

转化两个大数的 ，再用倍增求答案。

题意

题目

给你 ，其中 ，让你求 个 拼接起来的数和 个 拼接起来的数的最小公倍数。

思路

我们构造一个函数 表示 个 拼接起来，用数学语言表述就是：

同时又有 ，那么我们要求的就转化成了：

因为 与 都比较好求，所以此时的问题就转移到了怎么求 上来。

我们尝试感性理解一下。可以发现：

此时答案就变成了：

我们把这个式子分成两组：

对于每一组单独用倍增计算即可。详见代码。

提交记录 | 快得飞起

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, b, p, d;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int qpow(int x, int y) { // 快速幂
    int ans = 1;
    while (y) {
        if (y & 1) ans = (ans * x) % p;
        y >>= 1;
        x = (x * x) % p;
    }
    return ans;
}

int cal(int x, int y) { // 倍增计算答案
    int now = 1, npow = qpow(10, y), ans = 0;
    while (x) {
        if (x & 1) ans = ((ans * npow) % p + now) % p;
        x >>= 1;
        now = ((now * npow) % p + now) % p;
        npow = (npow * npow) % p;
    }
    return ans;
}

void solve() {
    cin >> a >> b >> p;
    d = gcd(a, b);
    cout << cal(a, 1) * cal(b / d, d) % p << endl; // 对于第二组，gcd(a, b) 是一个循环节，一共有 b / gcd(a, b) 个循环。
    return;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while (T--) solve();
    return 0;
}

最后

问我为什么不推式子？如果你直接开始推式子，你会推出一个带分母的式子。有分母就要求逆元，但是本题中并未保证模数的性质，所以不能直接求逆元。