Goldbach
题意
哥德巴赫猜想:输入一个T(100),输入一个偶数n(2<n<2^63),输出任意一组素数a,b,使得a+b=n。
思路
a和b必定为一大一小,从小的入手,用埃氏筛筛出1e6内的所有素数prim[](猜想到小的那个素数一定不超过1e6),然后遍历prim[],算出n-prim[i],用基于概率的素数测试算法MillerRabin判断它是不是素数即可。
这里注意,由于2^63次过大,在相乘得过程中会超longlong,因此要改用unsigned long long。
做题的时候,遇到范围是2^63,取模2^64的这种题目。遇到这种限制条件时就要想到用unsigned long long类型。这样,如果ull类型的整数溢出了,就相当于取模2^64了。因为ull的范围是[0,2^64-1]。而ll的范围是[-2^63,2^63-1],因为有符号的第63位表示“正负”而不表示数值。
附一个公式:(1+a1)(1+a2)(1+a3)……(1+an-1)(1+an) = 1+sum{ai}+sum{ai·aj}+sum{ai·aj·ak}+……+sum{a1·a2·…·an}
看!代码
1 |
|