文章目录Python的数字哈希运算解读官方文件P2613 【模板】有理数取余题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1说明/提示最后那么我们算哈希值有哪些应用呢Python的数字哈希运算解读官方文件官方的解说其实算哈希值对于不同的数据类型是有一定不同的总结来说就是除复数外如果数字的值相等那它的哈希值就会一定相等底层统一按有理数m / n m/nm/n计算的就是说1.对于整数 int、分数 Fraction、有限小数 float/Decimal等数据类型而言全部转有理数分子分母m / n m/nm/n用质数模 P快速幂求逆元算哈希在这里先来看看啥是乘法快速幂我先举个例子计算a^b%mod,在数据量很大的时候他的时间复杂度为O(b)在大数据下是很容易超时的那么乘法快速幂是怎么做到的呢先看下面的代码# 乘法快速幂defquick_pow(a,n,mod):res1a%mod# 防止溢出whilen0:ifn1:res(res*a)%mod a(a*a)%mod n1returnres aint(input(请输入底数: ))bint(input(请输入指数: ))modint(input(请输入模数: ))print(quick_pow(a,b,mod))# 那它的原理是啥呢就是说我如果能吧我的指数变为二进制比如说132^32^22^0,那我们在计算a^13次方的时候就可以:# 把13换为二进制的形式然后再把a^13转化为a^8*a^4*a^1,这样不需要逐个乘 a只需不断把底数平方就行了这样效率更高# 再看二进制每一位是否为 1为 1就乘进答案最后看要不要取模运算要的话就在乘的时候一起取了。2.对于大的质数质数模 P 压缩用大质数 P sys.hash_info.modulus 做模运算控制哈希值范围、减少碰撞3.对于一些正负无穷、NaN、复数有专门的处理常见的如下下面对官方代码进一步分析importsys,mathdefhash_fraction(m,n):Compute the hash of a rational number m / n. Assumes m and n are integers, with n positive. Equivalent to hash(fractions.Fraction(m, n)). Psys.hash_info.modulus# 移除 P 的公因数。 如果 m 和 n 互质则不需要。whilem%Pn%P0:m,nm//P,n//Pifn%P0:hash_valuesys.hash_info.infelse:# 费马小定理pow(n, P-1, P) 等于 1\n # 则 pow(n, P-2, P) 等于 n 除以 P 的余数的倒数。hash_value(abs(m)%P)*pow(n,P-2,P)%P# 解决负数和哈希冲突问题ifm0:hash_value-hash_valueifhash_value-1:hash_value-2returnhash_valuedefhash_float(x):Compute the hash of a float x.ifmath.isnan(x):returnobject.__hash__(x)elifmath.isinf(x):returnsys.hash_info.infifx0else-sys.hash_info.infelse:returnhash_fraction(*x.as_integer_ratio())defhash_complex(z):Compute the hash of a complex number z.hash_valuehash_float(z.real)sys.hash_info.imag*hash_float(z.imag)# 带正负号的约减求余运算 2**sys.hash_info.widthM2**(sys.hash_info.width-1)hash_value(hash_value(M-1))-(hash_valueM)ifhash_value-1:hash_value-2returnhash_value对于这段代码我们可以拆开来看约去 P 公因子whilem%Pn%P0:m,nm//P,n//P其实就是分子分母同时含因子 P 时约分提前消去分子分母公共的 P 因子防止算出来的哈希值不相等就是说在数学上我们认为1/27/14的且按规则它们的哈希值也理应要相等而在不约分前实际上是不相等的所以要不断地去约分。2.如果分母是p的倍数ifn%P0:hash_valuesys.hash_info.inf#所以这里就返回了一个特殊常量此时就是说它的分母就是p的倍数了那它就无法正常求逆啥意思就是说对有理数 x n/m正常哈希公式hash(x)(∣m∣⋅n^ −1)modP其中 n^−1是n在模 P下的乘法逆元,那入如果分母是p的倍数也就是说n的逆元就不存在了在数学上存在逆元的充要条件是二者互质可以进行证明①首先乘法逆元是指如果存在整数 x 使得 ⋅≡1(mod )那么 就是 模 的乘法逆元根据定义已知存在整数x,y满足axby1,证明gcd(a,b)1如果说a,b的gcd为1那它一定可以整除a,b,那我变成了一个线性表达也一定能够整除且没有其他因子即证明。②所以反过来说如果gcd(a,b)1那a/b就一定存在逆元的3.利用费马小定理来求模逆元hash_value(abs(m)%P)*pow(n,P-2,P)%P在解释之前先看啥是费马小定理就是说如果说P是一个质数存在一个a和P互质就一定有a^(p−1)≡1(modp pp)。就是说把 a 的 (p−1) 次方除以质数 余数一定是1因此我们利用它来求a^(p-2) ,在p很大的时候直接乘在数据量超10的8次方那一定会超时的这个时候只要在a^(p-1) 再除一个a就是说当 p 是质数时 a 的乘法逆元就是 a^(p−2) (mod p),那么官方文件给出的式子就是说计算 m / n % P 在数学上等于 m * n^(-1) % P。根据费马小定理n 的逆元就是 n^(P-2) % P。Python 直接调用内置的 pow(n, P-2, P)底层就是快速幂来极速计算逆元然后乘上分子取模很快可以得出得出分数的哈希值。基于此我们来看一个题目引用洛谷P2613P2613 【模板】有理数取余题目描述给出一个有理数c a b c\frac{a}{b}cba​求c m o d 19260817 c \bmod 19260817cmod19260817的值。这个值被定义为b x ≡ a ( m o d 19260817 ) bx\equiv a\pmod{19260817}bx≡a(mod19260817)的解。输入格式一共两行。第一行一个整数a aa。第二行一个整数b bb。输出格式一个整数代表求余后的结果。如果无解输出Angry!。输入输出样例 #1输入 #1233 666输出 #118595654说明/提示对于所有数据保证0 ≤ a ≤ 10 10001 0\leq a \leq 10^{10001}0≤a≤10100011 ≤ b ≤ 10 10001 1 \leq b \leq 10^{10001}1≤b≤1010001且a , b a, ba,b不同时是19260817 1926081719260817的倍数。这个题在一开始看的时候就会发现它给的a,b的量极大10^10001对于Python这种不是很快的语言来说直接算那是一定超时的那咋搞其实就是说他要求我们可以引入费马小定理要求a/b(mod c)就是求a⋅b^(mod−2)(mod mod),那代码如下defquick_pow(a,n,mod):res1a%modwhilen0:ifn1:#就是看它的二进制最后一位是否是1resres*a%mod aa*a%mod n1returnres mod19260817#他其实是个质数# 读取超长数字字符串a_strinput().strip()b_strinput().strip()# 大数逐位取模计算aa0forchina_str:a(a*10int(ch))%mod#这里进行了优化就是对于一个超长数字按位取模使它不那么大# 大数逐位取模计算bb0forchinb_str:b(b*10int(ch))%modifb0:#判定分母为0print(Angry!)else:# 根据推论来写b_invquick_pow(b,mod-2,mod)ans(a*b_inv)%modprint(ans)4.处理负数和哈希冲突ifm0:#哈希值为负那就转正hash_value-hash_valueifhash_value-1:#遇到 -1 替换成 -2hash_value-25.对于float类型这个其实还是调用了和int类型相似的取哈希值的方法defhash_float(x):Compute the hash of a float x.ifmath.isnan(x):#判断是否是数字returnobject.__hash__(x)elifmath.isinf(x):#特判是否是无穷returnsys.hash_info.infifx0else-sys.hash_info.infelse:# 这个和上面讲int的类似,所以在计算的时候hash(5) hash(5.0)returnhash_fraction(*x.as_integer_ratio())6.对于复数而言对于复数而言其实还是按int类型取哈希值的规则对实部和虚部进行运算在对算出来的值加权求和得到初始哈希值规则就是实部哈希 系数 × 虚部哈希defhash_complex(z):Compute the hash of a complex number z.hash_valuehash_float(z.real)sys.hash_info.imag*hash_float(z.imag)# 哈希数值范围上限M由Python哈希位宽决定M2**(sys.hash_info.width-1)# 按位运算实现带符号截断把哈希值约束到合法有符号整数区间hash_value(hash_value(M-1))-(hash_valueM)ifhash_value-1:hash_value-2returnhash_value最后那么我们算哈希值有哪些应用呢实际上哈希在实际应用有这些应用而他的计算逻辑也同样应用广泛以上就是我在对官方文件的数字哈希的理解还很浅希望大佬们多提意见