高坪网站建设WordPress主题 luo

高坪网站建设,WordPress主题 luo,医疗器械四大龙头企业,创意产品设计获奖作品一、雷劈数的定义背景#xff1a;有个数学家走在路上看见一个 3025 的路牌被劈成 30 和 25 了#xff0c;他发现 (3025)23025#xff0c;因此称这种数为雷劈数。比较小的雷劈数有 81(81)2,100(100)2。雷劈数的定义大概为#xff1a;将数 N的十进制表示从某处分成两半 a和 b…一、雷劈数的定义背景有个数学家走在路上看见一个 3025 的路牌被劈成 30 和 25 了他发现(3025)23025因此称这种数为雷劈数。比较小的雷劈数有81(81)2,100(100)2。雷劈数的定义大概为将数N的十进制表示从某处分成两半a和bb可以包含前导0但不能为空那么(ab)2N。二、雷劈数的求法因为b可以包含前导0所以考虑直接枚举b的位数n。这个时候十进制拼接就可以表示为10nab。于是我们的方程变成了这样(ab)210nab展开移项a22abb2−10na−b0a2(2b−10n)ab2−b0这是一个关于a的二次方程想要有整数解必须满足判别式Δ(2b−10n)2−4(b2−b)为完全平方数设为c2。因此4b2−4⋅10nb102n−4b24bc2即4(10n−1)b102n−c2。b也要是整数因此102n−c2需要是4(10n−1)的倍数。我们只需要找出符合这个条件的c即可。首先显然102n是4的倍数因此c只要是偶数就可以满足4的条件我们之后再带上这个偶数的条件。现在去掉4之后我们就需要找出c2≡102n≡1(mod10n−1)因为10n≡1(mod10n−1)。首先P10n−1显然不是一个质数我们先考虑将其质因数分解为∏ipaii。如果我们对于所有的paii求出它们的合法解那么将所有的可能组合全都用 exCRT 合并起来就可以获得P的所有合法解。现在问题变成求c2≡1(modpaii)。注意这不是一般的二次剩余问题因为我们寻找的数的平方是1。显然的这种情况下c只能为1或paii−1把1移到c2处然后因式分解即可证明。于是我们求出了所有合法的c。如果遇到了奇数跳过即可。对于每一个c其有唯一对应的两组对偶解b102n−c24(10n−1),a10n±c2−b。容易发现满足上面条件的c所对应的a和b一定合法。于是整个问题就解决了回顾一遍整体的流程枚举b的位数n将P10n−1分解为k∏i1paii对于每一个paii的两种选法将它们任意组合形成2k种不同的解每一种都用 exCRT 合并得到对应的c在合法的c中加上P1然后枚举所有的c判断是否是偶数对前几步得到的每一个偶数c都还原出对应的两组a,b最后将得到的所有(ab)2从小到大排序。实现有点困难因为我带着高精度写的所以写了 17KB目前 15 秒能算出1050以内所有雷劈数。代码就不给了upd: 拿 python 重写了一下只有不到 2kb 而且 0.5 秒能算1060我回去加一下优化的高精度库应该还能加速Code实际上现在瓶颈在于质因数分解在目前能够快速分解的范围内对应到输入就是 65 位左右基本都能一秒跑完了所以可能也就这样了吧。其它的加速就又回归到了质因数分解而这并不是我想研究的部分如果有人会更快速的分解10n−1也可以在此基础上进行优化。特别鸣谢liqingyang刷视频的时候看到了这个问题Grammar__hbw把倍数关系转化为了剩余问题zhouyuhang提出了剩余问题的大体解决方案OEIS A102766验证了程序的较小项的正确性我自己写调了一晚上的史山