问题:
有一个 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 了。此时如何继续拆分?
1
akira 358 天前
能用数组么
|
3
UIXX 358 天前
后面这个推导不对,x_hi 也要模处理
|
4
akira 358 天前
xh xl 不够用,那就 x1,x2,x3,x4 咯
|
5
MoYi123 358 天前
龟速乘
|
7
KnightZJ 357 天前 via Android 2
用类似快速幂的思想用快速乘能求出前半的(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; } |