中国剰余定理 (CRT) 使いました記念

ライブラリ 
// 約数一覧を返します
vector<ll> calc_devisors(ll a){
    vector<ll> ret;
    for(ll i=1; i*i<=a; i++){
        if(a%i!=0) continue;
        ret.push_back(i);
        ll another = a/i;
        if(i!=another) ret.push_back(another);
    }
    sort(ALL(ret), greater<ll>()); // 使いやすいように大きい順にソートしておく
    return ret;
}

// drken's lib
// https://qiita.com/drken/items/ae02240cd1f8edfc86fd
// 負の数にも対応した mod
// 例えば -17 を 5 で割った余りは本当は 3 (-17 ≡ 3 (mod. 5))
// しかし単に -17 % 5 では -2 になってしまう
inline long long super_mod(long long a, long long m) {
    return (a % m + m) % m;
}

// 拡張 Euclid の互除法
// ap + bq = gcd(a, b) となる (p, q) を求め、d = gcd(a, b) をリターンします
long long extGcd(long long a, long long b, long long &p, long long &q) {  
    if (b == 0) { p = 1; q = 0; return a; }  
    long long d = extGcd(b, a%b, q, p);  
    q -= a/b * p;  
    return d;  
}

// 中国剰余定理
// リターン値を (r, m) とすると解は x ≡ r (mod. m)
// 解なしの場合は (0, -1) をリターン
// 入力：
// m1で割った余りがb1
// m2で割った余りがb2
PII ChineseRem(long long b1, long long m1, long long b2, long long m2) {
  long long p, q;
  long long d = extGcd(m1, m2, p, q); // p is inv of m1/d (mod. m2/d)
  if ((b2 - b1) % d != 0) return make_pair(0, -1);
  long long m = m1 * (m2/d); // lcm of (m1, m2)
  long long tmp = (b2 - b1) / d * p % (m2/d);
  long long r = super_mod(b1 + m1 * tmp, m);
  return make_pair(r, m);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    
    auto Y = calc_devisors(2*N);
    ll mi=inf;

    for(ll a : Y){
      ll b = 2*N/a;
      // aで割って0
      // bで割って-1であるものは？
      auto pa = ChineseRem(0,a,-1,b);
      if(pa.first==0)continue;
      ll k = pa.first;
      ll m = pa.second;
      chmin(mi,k);
    }
    p(mi);
    
    return 0;
}

追記