競プロ 数論変換 除数 一覧 ( FFT NTT MOD 一覧 )

#include <vector>
// m の倍数 + 1 の形の素数 p のうち、 minP <= p <= maxP を満たすものを小さい順に、最大 num 個列挙する。
// 32 ビット符号なし整数の範囲を想定
std::vector<unsigned int> GetPrime_MultiplePlusOne(unsigned int m, unsigned int minP, unsigned int maxP, unsigned int num);


#include <algorithm>
#include <cassert>

bool IsPrime32(unsigned int x) noexcept {
    if(x <= 1) return false;
    if(x % 2 == 0) return x == 2;
    using u32 = unsigned int;
    using u64 = unsigned long long;
    u32 d = x-1;
    int s = 0;
    int q = 31;
    while(!(d&1)){ d >>= 1; s++; }
    while(!(d >> q)) q--;
    u32 r = x; for(int t=0; t<6; t++) r*=2-r*x;
    u64 n2 = -(u64)x % x;
    auto red = [=](u64 t) -> u32 {
        u32 s = ((u64)((u32)t*r)*x) >> 32;
        t >>= 32;
        return (t >= s) ? t-s : t+x-s;
    };
    u32 one = red(n2);
    for(u32 base : { 2, 7, 61 }){
        if(base%x==0) continue;
        u32 a = base = red(base%x*n2);
        for(int e=q-1; e>=0; e--){ a = red((u64)a*a); if((d>>e)&1) a = red((u64)a*base); }
        if(a == one) continue;
        for(int t=1; t<s&&a!=x-one; t++) a = red((u64)a*a);
        if(a != x-one) return false;
    }
    return true;
}

std::vector<unsigned int> GetPrime_MultiplePlusOne(unsigned int m, unsigned int minP, unsigned int maxP, unsigned int num){
    if(num == 0) return {};
    std::vector<unsigned int> buf;
    assert(m >= 1);
    if(m <= 2 && minP <= 2 && 2 <= maxP) buf.push_back(2);
    if(m % 2 == 1){ m *= 2; } // primes are odd except "2"
    if(minP < 3) minP = 3;
    if(minP > maxP) return buf;
    for(unsigned int p = (minP-1)/m*m+1; buf.size() < num; p += m){
        if(IsPrime32(p)){
            buf.push_back(p);
        }
        if(maxP - p < m) break;
    }
    return buf;
}