[数论]Miller-Rabin素性测试

如果给出一个正奇数 n,要判断它是不是素数,有一个最简单暴力的方法,就是从 2 开始一直试到 \sqrt n,这样的话能保证结果绝对正确,但是,时间复杂度也就是 \Theta (\sqrt n),当 n 的规模到达 10^{30} 甚至更高的级别的时候,就不能在可以忍受的时间内看到结果了。尤其是构造 RSA 密码体制时所需要用到的,找一个极大的素数。

那么,有没有一个比较快的方法来判断一个数是不是素数呢?

(more…)

Read More

FFT用到的各种素数

是这样的,这几天在写 FFT,由于是在模意义下的,需要各种素数……

然后就打了个表方便以后查了、

如果 r \cdot 2^k + 1 是个素数,那么在\bmod r \cdot 2^k + 1意义下,可以处理 2^k 以内规模的数据,

2281701377=17\cdot 2^{27}+1 是一个挺好的数,平方刚好不会爆 long long

1004535809=479\cdot 2^{21}+1 加起来刚好不会爆 int 也不错

还有就是 998244353=119 \cdot 2^{23}+1

下面是刚刚打出来的表格(g\bmod (r \cdot 2^k + 1)的原根)

(more…)

Read More

[c++11]Sequenced before 规则和求值顺序

任何 C++ 操作符的求值顺序都是 unspecified(后面提到的除外),unspecified 也就是标准没有指定,可以由编译器决定,这包括在函数调用表达式中函数参数的求值顺序以及任何表达式的子表达式的求值顺序。编译器可以按照任意顺序将它们求值,对于相同的表达式,编译器也可以选择不同的顺序将它们求值。

在 C++ 中,没有什么从左到右或者从右到左的求值顺序,只有操作符从左到右和从右到左的结合性。就比如说表达式f1() + f2() + f3() 会通过加法操作符从左到右的结合性被解析为 (f1() + f2()) + f3(),但是对 f3 的调用可能会最先执行,然后是 f1,最后是 f2,因为它们的求值顺序是 unspecified。

C++ 是一个注重效率的语言,标准不指定一些表达式的求值顺序就是为了让编译器能做尽可能多的优化,即便要牺牲掉例如 i=i++ 这样表达式的正确性(据说在 Java 中就没这些问题,这个表达式的结果是确定的)。

(more…)

Read More

终于配置好邮件服务了QAQ

用的是 sendmail + dovecot + sasl2 + roundcube、 实际上发邮件本来昨天九点多就弄好了、结果发了一封给自己的 gmail 邮箱、发现居然拒收 google 了老半天才知道原来各种反垃圾邮件机制(果然能长姿势!)

然后又去设置RDNS(以前还真不知道有这货)、从域名提供商(好吧找它是我逗QAQ)找到服务器提供商 结果居然因为被 firefox 坑了修改的界面出不来弄到早上两点多才发现换 chrome 开掉后居然可以QAQ 接着 SPF记录、DKIM 什么什么的…… 最后 gmail 终于收了邮件了QAAAAAQ

早上开始弄 imap 等、又被 saslauthd 登陆啥的坑了大半天终于弄好了 TLS、最后套上 roundcube webmail!成了!!!

然后看我的邮箱 miskcoo@miskcoo.com

Read More