/ FFT

适合NTT的模数

本来用std::set存被线性筛筛掉的数,结果跑到1m左右内存就炸了,电脑完全卡死。记录质数倒不怎么担心,要筛出后面的质数需要的质数数量是比较少的。

于是我改成bitset+vector+-O2,秒出答案。

我可能会用998244353998244353(UOJ模数),924844033924844033(AtCoder模数)以及2267+12^{26}* 7+1。这几个比较好记,而且已经够处理P109P\leq10^9以及n106n\leq10^6以内的乘法了。

记录一些2121次NTT及以上的:

  • 23068673=221×11+123068673=2^{21}\times11+1
  • 69206017=221×3×11+169206017=2^{21}\times3\times11+1
  • 81788929=221×3×13+181788929=2^{21}\times3\times13+1
  • 104857601=222×52+1104857601=2^{22}\times5^{2}+1
  • 111149057=221×53+1111149057=2^{21}\times53+1
  • 113246209=222×33+1113246209=2^{22}\times3^{3}+1
  • 132120577=221×32×7+1132120577=2^{21}\times3^{2}\times7+1
  • 136314881=221×5×13+1136314881=2^{21}\times5\times13+1
  • 138412033=222×3×11+1138412033=2^{22}\times3\times11+1
  • 155189249=222×37+1155189249=2^{22}\times37+1
  • 163577857=222×3×13+1163577857=2^{22}\times3\times13+1
  • 167772161=225×5+1167772161=2^{25}\times5+1
  • 169869313=221×34+1169869313=2^{21}\times3^{4}+1
  • 186646529=221×89+1186646529=2^{21}\times89+1
  • 199229441=221×5×19+1199229441=2^{21}\times5\times19+1
  • 211812353=221×101+1211812353=2^{21}\times101+1
  • 230686721=222×5×11+1230686721=2^{22}\times5\times11+1
  • 249561089=221×7×17+1249561089=2^{21}\times7\times17+1
  • 257949697=221×3×41+1257949697=2^{21}\times3\times41+1
  • 270532609=221×3×43+1270532609=2^{21}\times3\times43+1
  • 274726913=221×131+1274726913=2^{21}\times131+1
  • 377487361=223×32×5+1377487361=2^{23}\times3^{2}\times5+1
  • 383778817=221×3×61+1383778817=2^{21}\times3\times61+1
  • 387973121=221×5×37+1387973121=2^{21}\times5\times37+1
  • 415236097=222×32×11+1415236097=2^{22}\times3^{2}\times11+1
  • 459276289=221×3×73+1459276289=2^{21}\times3\times73+1
  • 463470593=221×13×17+1463470593=2^{21}\times13\times17+1
  • 469762049=226×7+1469762049=2^{26}\times7+1
  • 576716801=221×52×11+1576716801=2^{21}\times5^{2}\times11+1
  • 595591169=223×71+1595591169=2^{23}\times71+1
  • 597688321=221×3×5×19+1597688321=2^{21}\times3\times5\times19+1
  • 635437057=221×3×101+1635437057=2^{21}\times3\times101+1
  • 639631361=221×5×61+1639631361=2^{21}\times5\times61+1
  • 645922817=223×7×11+1645922817=2^{23}\times7\times11+1
  • 648019969=221×3×103+1648019969=2^{21}\times3\times103+1
  • 666894337=222×3×53+1666894337=2^{22}\times3\times53+1
  • 683671553=222×163+1683671553=2^{22}\times163+1
  • 710934529=221×3×113+1710934529=2^{21}\times3\times113+1
  • 715128833=221×11×31+1715128833=2^{21}\times11\times31+1
  • 740294657=221×353+1740294657=2^{21}\times353+1
  • 754974721=224×32×5+1754974721=2^{24}\times3^{2}\times5+1
  • 786432001=221×3×53+1786432001=2^{21}\times3\times5^{3}+1
  • 799014913=221×3×127+1799014913=2^{21}\times3\times127+1
  • 824180737=221×3×131+1824180737=2^{21}\times3\times131+1
  • 880803841=223×3×5×7+1880803841=2^{23}\times3\times5\times7+1
  • 897581057=223×107+1897581057=2^{23}\times107+1
  • 899678209=221×3×11×13+1899678209=2^{21}\times3\times11\times13+1
  • 918552577=222×3×73+1918552577=2^{22}\times3\times73+1
  • 924844033=221×32×72+1924844033=2^{21}\times3^{2}\times7^{2}+1
  • 935329793=222×223+1935329793=2^{22}\times223+1
  • 943718401=222×32×52+1943718401=2^{22}\times3^{2}\times5^{2}+1
  • 950009857=221×3×151+1950009857=2^{21}\times3\times151+1
  • 962592769=221×33×17+1962592769=2^{21}\times3^{3}\times17+1
  • 975175681=221×3×5×31+1975175681=2^{21}\times3\times5\times31+1
  • 985661441=222×5×47+1985661441=2^{22}\times5\times47+1
  • 998244353=223×7×17+1998244353=2^{23}\times7\times17+1
  • 1004535809=221×479+11004535809=2^{21}\times479+1
  • 1012924417=221×3×7×23+11012924417=2^{21}\times3\times7\times23+1