P10446 64位整数乘法 题解

· · 题解

提供一种非常优雅的方法。有一种数据类型为 __int128，它能存储最大为 2^{127}-1 的整数，而本题 a\times b 最大可能为 10^{36}，正好可以用 __int128 运算。__int128 并不能用 cin 或 scanf 读入，也不能用 cout 或 printf 输出。但是输入数据不超过 10^{18}，所以我们可以先用 long long 类型读入 a,b,p，再将其转换为 __int128 类型运算；注意到 p 不超过 10^{18}，所以最终运算结果也不超过 10^{18}-1，我们可以把 __int128 类型的运算结果转换为 long long 再输出。由此省去了写快读或快输。代码如下：

#include <cstdio>

long long A, B, P, ANS;
__int128 a, b, p, ans;

int main() {
    scanf("%lld%lld%lld", &A, &B, &P);
    a = A;
    b = B;
    p = P;
    ans = a * b % p;
    ANS = ans;
    printf("%lld", ANS);
    return 0;
}

AC 链接