关于 Montgomery 乘法的几个疑问
  • 板块学术版
  • 楼主Tsukimaru
  • 当前回复7
  • 已保存回复7
  • 发布时间2021/3/22 11:47
  • 上次更新2023/11/5 01:45:04
查看原帖
关于 Montgomery 乘法的几个疑问
45398
Tsukimaru楼主2021/3/22 11:47
  1. 为什么有的代码在 Reduce 的时候不判断 if (x >= P) x -= P; 而只在最后输出时判断，却是正确的？我的代码去掉了中间部分的判断却会导致 Wrong Answer。
  2. 为什么如果将 min_25 在其博客给出的实现改为利用 32/64bit 整数求解 108! mod (109+7)10^8! \bmod (10^9 + 7)，Montgomery 乘法会没有暴力快？Montgomery 乘法优化是否确实效果不明显（在 NOI 系列比赛上）？
2021/3/22 11:47