是否不存在 2022397710683865089 的倍数，在 256 进制下每一位都小于 26？
我在 Codeforces 网站上看到一道题目，涉及仅包含小写拉丁字母的字符串的子串相等比较。有人使用了字符串哈希算法解出，是 和 的双哈希。因为 ，所以...
- 50 个点赞 👍
根据生日悖论，在整体选项数目约为N的情况下，我们大概需要随机产生 \sqrt{N} 个随机样本，可以找到两个样本发生碰撞。而这里N=2022397710683865089, \sqrt{N} 略大于 10^9 ,这种规模在现在计算机算力下寻找碰撞还是可行的。
所以我们可以随机产生若干组 \sum{a_i 256^i} 数据，直到两组模2022397710683865089相等，那么它们的差就是2022397710683865089的倍数，唯一的问题是两者差可以产生某些系数是负数。
但是如果我们事先计算好 A=\sum{25*256^i} \pmod {2022397710683865089} , 然后随机产生若干组数据，直到两者之和关于2022397710683865089的余数为A，那么设两者分别为 \sum{a_i 256^i} ;\sum{b_i 256^i} ,其中 0\le a_i\le 12; 0\le b_i\le12 , 那么 \sum{(25-a_i-b_i)256^i} 就是2022397710683865089的倍数，可以符合条件。
所以现在的算法就可以是每次随机产生一组 \sum{a_i 256^i} ，其中 0\le a_i\le12 , 计算其模2022397710683865089的余数X，并且在一个map中匹配，如果遇到匹配的，那么已经找到结果；不然，将映射关系A-X => \sum{a_i 256^i} 加入map中。
这个算法唯一的问题是空间复杂度有些大，预期map最终规模到达数G项，比如这里 a_i 可以有16个，每个4比特，共64比特。每个关于2022397710683865089的余数也64比特。所以每项16字节，但是map本身数据结构占用空间会更大一些，所以最终将需要几百G内存空间（或者通过外存储）
用计算机搜索上面的数据竟然没有找到，然后改为21个，每个0～7 （3比特），找到了
16110906371565107114088456463416962548455164085513=2022397710683865089*7966240411791839601065921611017
对应256进制各位为
? v=[9,5,8,11,11,3,6,7,6,4,10,13,7,13,3,1,6,7,6,6,11] %1 = [9, 5, 8, 11, 11, 3, 6, 7, 6, 4, 10, 13, 7, 13, 3, 1, 6, 7, 6, 6, 11] ? w=0;for(u=1,21,w+=v[u]*256^(u-1));w %2 = 16110906371565107114088456463416962548455164085513 ? %2 /2022397710683865089 %3 = 7966240411791839601065921611017前面仅适用16个数没有找到结果，应该是数据没有随机产生而有一定规律的原因，改为随机数（rdrand)后,可以找到更小的结果了
? v=[22,12,14,15,3,17,13,21,13,12,14,4,12,11,4,16] %5 = [22, 12, 14, 15, 3, 17, 13, 21, 13, 12, 14, 4, 12, 11, 4, 16] ? w=0;for(u=1,length(v),w+=v[u]*256^(u-1));w %6 = 21288641178491305527004089323734567958 ? w/M %7 = 10526436549066624022 ? v=[22,21,18,17,10,23,21,25,4,14,9,5,10,23,14,10] %8 = [22, 21, 18, 17, 10, 23, 21, 25, 4, 14, 9, 5, 10, 23, 14, 10] ? w=0;for(u=1,length(v),w+=v[u]*256^(u-1));w %9 = 13365439403129527017108993907161699606 ? w/M %10 = 6608709717442303254 ? v=[25,9,5,5,21,10,20,25,13,18,4,13,5,12,4,18] %11 = [25, 9, 5, 5, 21, 10, 20, 25, 13, 18, 4, 13, 5, 12, 4, 18] ? w=0;for(u=1,length(v),w+=v[u]*256^(u-1));w %12 = 23947116900646907489316813862934481177 ? w/M %13 = 11840953326904871193 ? v=[7,14,17,3,13,9,18,20,7,21,14,18,14,15] %14 = [7, 14, 17, 3, 13, 9, 18, 20, 7, 21, 14, 18, 14, 15] ? w=0;for(u=1,length(v),w+=v[u]*256^(u-1));w %15 = 305350926084413285478724222914055 ? w/M %16 = 150984608255495 ? v=[16,19,17,25,17,4,17,4,11,17,6,8,13,11] %18 = [16, 19, 17, 25, 17, 4, 17, 4, 11, 17, 6, 8, 13, 11] ? w=0;for(u=1,length(v),w+=v[u]*256^(u-1));w %19 = 224138954966970736913977692984080 ? w/M %20 = 110828327080720==================
由于发现上面随机搜素得到结果仅M=2022397710683865089的 10^{14} 倍左右，考虑到实际上最小值可能会更小，于是试着写了一个从小到达穷举M的所有倍数的程序，结果发现可行，比如符合条件的最小的两个M的倍数为
399570568233696659924615960586 482826933321103562173598208264 ? 399570568233696659924615960586/2022397710683865089 %1 = 197572696074 ? dec256(x)={local(v,r);v=[];while(x>0, r=x%256;v=concat(v,r);x=(x-r)/256);v} %2 = (x)->local(v,r);v=[];while(x>0,r=x%256;v=concat(v,r);x=(x-r)/256);v ? dec256(399570568233696659924615960586) %3 = [10, 24, 0, 7, 18, 9, 23, 3, 3, 7, 21, 11, 5] ? 482826933321103562173598208264/2022397710683865089 %4 = 238739853576 ? dec256(482826933321103562173598208264) %5 = [8, 17, 1, 21, 15, 0, 14, 16, 22, 20, 25, 24, 6]继续搜索还有更多解
21159812990124519421490800036869 40569463943266575422535274335000 41998066124008896033080034528009 82241326808125838922727812105746 102290065467826344940701685910016 123603694930202511916441141315584 164082791611487977850921645053966 202907044144335292983773881635340 202989060075659743553330127378453 224138954966970736913977692984080 224216344324832963943073229312007 244186462983276954486239894045204 265495763163774625445539241721871 285304333116577247064887252226579 305350926084413285478724222914055 326347004503472631285123133150983 326500820975724278839371788519682 346310970923737134025665724482314 365724021399894405172778907537927 405727739481875214460523584749833 427597196706723621510210402847253 427833029110299719634015303959065 447246079586456990781128487014678 466499782688679145355133151810576 487332745619991778084782080722445 508090831233217456451293018132996上面列表包含了所有256进制下长度不超过14的解，比如最后一个
? dec256(508090831233217456451293018132996) %2 = [4, 18, 1, 12, 7, 21, 0, 2, 23, 3, 5, 2, 13, 25]对应C++搜索代码在
https://github.com/emathgroup/selectedTopics/blob/master/content/attached/files/gmpsrch.cpp
需要使用gmp和openmp,编译选项
g++ -O3 gmpsrch.cpp -ogmpsrch -fopenmp -lgmpxx -lgmp编辑于 2024-05-05 09:37・IP 属地上海查看全文>>
mathe - 17 个点赞 👍
这种反例不是随便构造吗？
256^2022397707666063360-1是2022397710683865089的倍数
每一位都是255
这个数字除以255之后每一位都是1
显然gcd(255,2022397710683865089)=1
于是
(256^2022397707666063360-1)/255是2022397710683865089的倍数
且这个数字256进制下每一位都是1碰撞的话，可以参考 @Lumina 的答案
发布于 2024-05-05 14:22・IP 属地安徽查看全文>>
知乎用户 - 11 个点赞 👍
查看全文>>
知乎用户 - 9 个点赞 👍
注意到， 9382481536280561972666655041858701312 和 7991127487437654305636369416915255563 是一组符合条件的碰撞（不是问题的解，但是根据题目描述，已经足够用）。
Python 3.12.0 (tags/v3.12.0:0fb18b0, Oct 2 2023, 13:03:39) [MSC v.1935 64 bit (AMD64)] on win32 Type "help", "copyright", "credits" or "license()" for more information. (9382481536280561972666655041858701312-7991127487437654305636369416915255563)%2022397710683865089 0 def f(x): while x!=0: print(x%256,end=',') x//=256 print() f(9382481536280561972666655041858701312) 0,8,6,2,3,9,10,0,4,7,0,12,14,0,15,7, f(7991127487437654305636369416915255563) 11,1,12,9,3,4,3,8,15,4,0,4,1,9,3,6,编辑于 2024-05-04 01:50・IP 属地加拿大查看全文>>
Lumina - 5 个点赞 👍
一看到哈希基本上可以认为是概率算法了。
别人这么做只是为了过题，毕竟比赛的时候概率过了也是过了，因为选择的模很大，出题人基本不可能为每个模考虑数据，多数只能依靠随机数据，哪怕提交后发现错了，那我换个模再交一次就是了。
类似的操作还有，如用哈希跑树，哈希跑图等，反正突出一个只要没撞上那我就过了。
发布于 2024-05-03 10:52・IP 属地广东查看全文>>
Lyric Law - 4 个点赞 👍
从数学上你完完全全可以证明这一点。
对于任何k进制，如果p和k互质，对于任何两个数码a，b，其中a-b和p互质，以及余数c，有完全只用a，b数码写成的k进制正整数是模p余c。
证明显然。
编辑于 2024-05-04 04:04・IP 属地美国查看全文>>
狗雷布是真的伊 - 2 个点赞 👍
查看全文>>
cancan123456 - 1 个点赞 👍
仅从整数考虑，每位小于26，你的边界条件要小于1880844493789993498。此后，256的0次幂为1（最小）以此递增，均会使某位大于26？。
发布于 2024-05-04 10:35・IP 属地安徽查看全文>>
XSBZYHZBYP