一个大数除法/取模相关的数学问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 542 天前的主题，其中的信息可能已经有所发展或是发生改变。

问题：

有一个 13 字节的无符号整数 x ，除以 D (D = 123^6)，求余数 r 和商 q 。
通过 r 、q ，还原 x 。

算法只用 u64/u32 等基本类型，不使用编译器 /平台提供的特性。

思路：使用 x_hi 和 x_lo 两个 u64 表示 x：

x = x_hi * 2^64 + x_lo （其中 0 <= x_lo < 256^8 ，0 <= x_hi < 256^5 ）

根据分配率公式：(a + b) % p = (a % p + b % p) % p

带入后，余数为：

r = x % D

  = (x_hi * 2^64 + x_lo) % D

  = (x_hi * (2^64 % D) + x_lo % D) % D

  = (x_hi * 3378380888563 + x_lo % 3462825991689) % D

但当 x 很大时，乘法的结果就超出 u64 了。此时如何继续拆分？

7 条回复 • 2023-05-30 01:29:45 +08:00

akira

2023-05-29 17:17:56 +08:00

能用数组么

iqoo

2023-05-29 17:24:19 +08:00

@akira 最好是用几个 u64 简单算出来，毕竟除数的已知的。之前用 gcc 的 __u128_t 类型，展开后一大堆逻辑。

UIXX

2023-05-29 17:52:31 +08:00

后面这个推导不对，x_hi 也要模处理

akira

2023-05-29 18:07:55 +08:00

xh xl 不够用，那就 x1,x2,x3,x4 咯

MoYi123

2023-05-29 18:29:23 +08:00

龟速乘

iqoo

2023-05-29 20:05:37 +08:00

@UIXX 这里省略了。因为 x_hi 小于 D ，所以模了之后还是本身。

KnightZJ

2023-05-30 01:29:45 +08:00 via Android

用类似快速幂的思想用快速乘能求出前半的(x_hi * 3378380888563)%D ，找了篇介绍的文章( https://www.cnblogs.com/jaszzz/p/12692716.html)和代码：
long long q_mul(long long a,long long b,long long mod)
// 快速计算 (a*b) % mod
{
long long ans=0;
while(b)
{
if(b&1)
ans =(ans+a)%mod;
b>>=1;
a=(a+a)%mod;
}
return ans;
}