math

ソースコード

 1// pow ----------------
 2long long pow_mod(long long a, long long b, const long long mod) {
 3    long long res = 1;
 4    while (b) {
 5        if (b & 1) res = res * a % mod;
 6        a = a * a % mod;
 7        b >>= 1;
 8    }
 9    return res;
10}
11
12long long pow(long long a, long long b) {
13    long long res = 1;
14    while (b) {
15        if (b & 1) res *= a;
16        a *= a;
17        b >>= 1;
18    }
19    return res;
20}
21// pow ----------------
22
23// factorial -----------------
24long long factorial(long long x) {
25  long long res = 1;
26  for (long long i = 1ll; i <= x; ++i) {
27    res *= i;
28  }
29  return res;
30}
31// factorial -----------------
32
33// get_primelist -----------------
34vector<int> get_primelist(int MAX) {
35  vector<int> is_prime(MAX+1, 1);
36  is_prime[0] = 0;
37  is_prime[1] = 0;
38  for (int i = 2; i < sqrt(MAX)+1; ++i) {
39    if (!is_prime[i]) continue;
40    for (int j = i+i; j < MAX+1; j+=i) {
41      is_prime[j] = 0;
42    }
43  }
44  return is_prime;
45}
46// get_primelist -----------------
47
48
49bool is_primell(long long n) {
50  if (n == 1) return false;
51  if (n == 2) return true;
52  if (!(n & 1ll)) return false;
53  vector<long long> p = {2, 7, 61, 325, 9375, 28178, 450775, 9780504, 1795265022};
54  long long d = n - 1;
55  long long dd = d & (-d);
56  long long cnt = 0;
57  while (dd) {
58    ++cnt;
59    dd >>= 1ll;
60  }
61  d >>= cnt - 1ll;
62  for (long long a : p) {
63    if (n <= a) break;
64    long long t = d;
65    long long y = pow_mod(a, t, n);
66    while (t != n-1ll && y != 1ll && y != n-1ll) {
67      y = pow_mod(y, 2ll, n);
68      t <<= 1ll;
69    }
70    if (y != n-1ll && (!(t&1ll))) return false;
71  }
72  return true;
73}

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/math/math.cpp