NTT有没有可能溢出
  • 板块P2000 拯救世界
  • 楼主uibn
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/6/18 11:36
  • 上次更新2023/11/4 21:46:44
查看原帖
NTT有没有可能溢出
60215
uibn楼主2021/6/18 11:36

如果四个相乘的数每一位都为9,那么两个数相乘第 ii 位就有 81i81i ,再乘一个数每一位就有 7291+2+...i 729 * (1+2+...i) 再乘一个数最大的数就有 s[1]+s[2]+...+s[100000] s[1]+s[2]+...+s[100000] ,其中 s[i]s[i]1+2+...+i 1+2+...+i ,最大可达到 10101414 次方,这样NTT还可以做吗?有没有可能超过NTT模数?

2021/6/18 11:36
加载中...