test/yosupo/Sample/fast_modinv.test.cpp

View this file on GitHub
Last update: 2024-06-05 19:06:59+07:00
Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "Misc/marco.hpp"
#include "Misc/debug.hpp"
const int INF=1e9;
const ll INFI=1e15;
//----------Author: Nguyen Ho Nam,UIT, Saigon-----------------
#include "Mod/mod_inv.hpp"
#include "NT/Fast_NT/fast_modinv.hpp"
void benchmark() {
   const int MOD1 = 998244353;  
  const int MOD2 = 1000000007; 
  
  fast_modinv fmi1(MOD1);
  fast_modinv fmi2(MOD2);
  
  vector<int> test_cases;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<int> dist(1, 10000000000);
  for (int i = 0; i < 5; i++) {
    test_cases.push_back(dist(rng));
  }
  
  
  cerr << "Benchmarking fast_modinv:\n";
  for (int tc : test_cases) {
    auto start = chrono::high_resolution_clock::now();
    int res1 = fmi1(tc);
    int res2 = fmi2(tc);
    auto end = chrono::high_resolution_clock::now();
    assert(res1 == inv_mod(tc, MOD1));
    assert(res2 == inv_mod(tc, MOD2));
    cerr << "Input: " << tc << ", Time: " << chrono::duration_cast<chrono::nanoseconds>(end - start).count() << " ns\n";
  }
  
  cerr << "\nBenchmarking inv_mod:\n";
  for (int tc : test_cases) {
    auto start = chrono::high_resolution_clock::now();
    int res1 = inv_mod(tc, MOD1);
    int res2 = inv_mod(tc, MOD2);
    auto end = chrono::high_resolution_clock::now();
    cerr << "Input: " << tc << ", Time: " << chrono::duration_cast<chrono::nanoseconds>(end - start).count() << " ns\n";
  }
}

int main() {
    FT;
    benchmark();
    int a,b; cin>>a>>b;
    cout<<a+b<<'\n';
    return 0;
}

#line 1 "test/yosupo/Sample/fast_modinv.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "Misc/marco.hpp"
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ods;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;

using ld = long double;
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
 
 
#define pii pair<int,int>
#define pll pair<ll,ll>
 
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ars(x) (x),(x+n)
 
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
 
#define For(i,a,b) for (int i=(a); i<(b); i++)
#define rep(i,a) For(i,0,a)
#define rev(i,a,b) for (int i=(a); i>(b); i--)
#define FOR(i,a,b) for (int i=(a); i<=(b); i++)
#define REP(i,a) FOR(i,1,a)
#define REV(i,a,b) for (int i=(a); i>=(b); i--)
 
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define FT ios_base::sync_with_stdio(false); cin.tie(nullptr);
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using vi=vector<int>;
using vll = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
 
#define vv(type, name, h, ...) \
  vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...)   \
  vector<vector<vector<type>>> name( \
      h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)       \
  vector<vector<vector<vector<type>>>> name( \
      a, vector<vector<vector<type>>>(       \
             b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
 
//template <class T>
//using ods =
//   tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#line 1 "Misc/debug.hpp"
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<>
void __print(const vector<bool> &x) {int f = 0; cerr << '{'; for (size_t i = 0; i < x.size(); ++i) cerr << (f++ ? ", " : ""), __print(x[i]); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { __print(H); if (sizeof...(T)) cerr << ", "; dbg_out(T...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:"; dbg_out(__VA_ARGS__);
#line 4 "test/yosupo/Sample/fast_modinv.test.cpp"
const int INF=1e9;
const ll INFI=1e15;
//----------Author: Nguyen Ho Nam,UIT, Saigon-----------------
#line 2 "Mod/mod_inv.hpp"

#line 4 "Mod/mod_inv.hpp"
#include <type_traits>

// gcd(a, m) != 1 return -1 
template <typename T>
T inv_mod(T a, T m) {
  if (m == 1) return 0;
  if (a >= m) a %= m;
  if (a < 0) a += m;
  if(__gcd(a,m)!=1) return -1;
  T b = m, s = 1, t = 0;
  while (true) {
    if (a == 1) return s;
    t -= b / a * s;
    b %= a;
    if (b == 1) return t + m;
    s -= a / b * t;
    a %= b;
  }
}
#line 3 "NT/Fast_NT/fast_modinv.hpp"
 
struct fast_modinv {
  using u32 = unsigned int;
  using u64 = unsigned long long;
 
  u32 mod;
  u32 ipow2[64], pre[2048 / 2];
 
  fast_modinv(u32 m) : mod(m), ipow2(), pre() {
    assert(mod % 2 == 1 && mod < (1LL << 30));
 
    // Precompute ipow2
    ipow2[0] = 1 % mod;
    for (int i = 1; i < 64; i++) {
      ipow2[i] = u64(ipow2[i - 1]) * ((mod + 1) / 2) % mod;
    }
 
    // Precompute pre for odd numbers
    pre[0] = 1 % mod;
    for (int i = 3; i < 2048; i += 2) {
      pre[i >> 1] = [this, i]() -> int {
        int x = i, y = mod, u = 1, v = 0, t = 0, tmp = 0;
        while (y > 0) {
          t = x / y;
          x -= t * y, u -= t * v;
          tmp = x, x = y, y = tmp;
          tmp = u, u = v, v = tmp;
        }
        return u < 0 ? u + mod : u;
      }();
    }
  }
 
  bool is_prime(u32 n) const {
    if (n == 1) return false;
    for (int p = 3; p * p <= n; p += 2) {
      if (n % p == 0) return false;
    }
    return true;
  }
 
  u32 inv(u32 a) const {
    if (mod == 1) {
      return 0;
    }
 
    u32 b = mod, s = 1, t = 0;
    int n = __builtin_ctz(a);
    a >>= n;
 
    while (a - b != 0) {
      if (is_prime(mod)) {
        if (a < 2048) break;
      }
      int m = __builtin_ctz(a - b);
      bool f = a > b;
      n += m;
      a = f ? (a - b) >> m : a;
      b = f ? b : -(a - b) >> m;
      u32 u = f ? s - t : s << m;
      t = f ? t << m : -(s - t);
      s = u;
    }
    return u64(s) * pre[a >> 1] % mod * ipow2[n] % mod;
  }
 
  u32 operator()(u32 a) const { return inv(a); }
};
#line 9 "test/yosupo/Sample/fast_modinv.test.cpp"
void benchmark() {
   const int MOD1 = 998244353;  
  const int MOD2 = 1000000007; 
  
  fast_modinv fmi1(MOD1);
  fast_modinv fmi2(MOD2);
  
  vector<int> test_cases;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<int> dist(1, 10000000000);
  for (int i = 0; i < 5; i++) {
    test_cases.push_back(dist(rng));
  }
  
  
  cerr << "Benchmarking fast_modinv:\n";
  for (int tc : test_cases) {
    auto start = chrono::high_resolution_clock::now();
    int res1 = fmi1(tc);
    int res2 = fmi2(tc);
    auto end = chrono::high_resolution_clock::now();
    assert(res1 == inv_mod(tc, MOD1));
    assert(res2 == inv_mod(tc, MOD2));
    cerr << "Input: " << tc << ", Time: " << chrono::duration_cast<chrono::nanoseconds>(end - start).count() << " ns\n";
  }
  
  cerr << "\nBenchmarking inv_mod:\n";
  for (int tc : test_cases) {
    auto start = chrono::high_resolution_clock::now();
    int res1 = inv_mod(tc, MOD1);
    int res2 = inv_mod(tc, MOD2);
    auto end = chrono::high_resolution_clock::now();
    cerr << "Input: " << tc << ", Time: " << chrono::duration_cast<chrono::nanoseconds>(end - start).count() << " ns\n";
  }
}

int main() {
    FT;
    benchmark();
    int a,b; cin>>a>>b;
    cout<<a+b<<'\n';
    return 0;
}