#1006716 (C++23) No.443 GCD of Permutation

提出ソース

結果

問題	No.443 GCD of Permutation
ユーザー	kusaf_
提出日時	2024-09-01 10:48:40
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 1,000 ms
コード長	8,376 bytes
コンパイル時間	3,540 ms
コンパイル使用メモリ	265,256 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-01 10:48:45
合計ジャッジ時間	4,593 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,948 KB
testcase_04	AC	3 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	3 ms 6,940 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,940 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	2 ms 6,940 KB
testcase_25	AC	3 ms 6,940 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	2 ms 6,944 KB
testcase_31	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll D_SI = 125;
struct lll : vector<ll> {
  static const ll BASE = 100000000;
  static const ll BASE_D = 8;
  ll sign;
  lll(ll n = 0): vector<ll>(D_SI, 0), sign(1) {
    if(n < 0) { sign = -1, n = -n; }
    (*this)[0] = n;
    this->normalize();
  }
  lll(ll size, ll n): vector<ll>(size, n), sign(1) {}
  lll &normalize() {
    ll c = 0;
    bool e = false;
    for(ll i = 0;; ++i) {
      if(i >= this->size()) { this->push_back(0); }
      if((*this)[i] < 0 && i + 1 >= this->size()) { this->push_back(0); }
      while((*this)[i] < 0) {
        (*this)[i + 1] -= 1;
        (*this)[i] += BASE;
      }
      ll a = (*this)[i] + c;
      (*this)[i] = a % BASE;
      if((*this)[i]) { e = 1; }
      c = a / BASE;
      if(c == 0 && i == this->size() - 1) { break; }
    }
    if(!e) { sign = 1; }
    return (*this);
  }
  friend lll abs(const lll &x) {
    lll z = x;
    if(z.sign == -1) { z.sign = 1; }
    return z;
  }
  lll operator-() const {
    lll r = *this;
    bool z = 1;
    for(ll i = 0; i < (ll)this->size(); i++) {
      if(r[i] != 0) {
        z = 0;
        break;
      }
    }
    if(!z) { r.sign = -r.sign; }
    return r;
  }
  lll &operator+=(const lll &r) {
    while(size() < r.size()) this->emplace_back(0);
    if(sign == r.sign) {
      for(ll i = 0; i < (ll)r.size(); i++) {
        (*this)[i] += r[i];
      }
    }
    else {
      if(sign == 1 && abs(*this) < abs(r)) { sign = -1; }
      else if(sign == -1 && abs(*this) <= abs(r)) { sign = 1; }
      if(abs(*this) >= abs(r)) {
        for(ll i = 0; i < (ll)r.size(); i++) { (*this)[i] -= r[i]; }
      }
      else {
        for(ll i = 0; i < (ll)size(); i++) { (*this)[i] = -(*this)[i]; }
        for(ll i = 0; i < (ll)r.size(); i++) { (*this)[i] += r[i]; }
      }
    }
    return this->normalize();
  }
  lll &operator-=(const lll &r) {
    while(size() < r.size()) { this->emplace_back(0); }
    if(sign == -r.sign) {
      for(ll i = 0; i < (ll)r.size(); i++) { (*this)[i] += r[i]; }
    }
    else {
      if(sign == 1 && abs(*this) < abs(r)) { sign = -1; }
      else if(sign == -1 && abs(*this) <= abs(r)) { sign = 1; }
      if(abs(*this) >= abs(r)) {
        for(ll i = 0; i < (ll)r.size(); i++) { (*this)[i] -= r[i]; }
      }
      else {
        for(ll i = 0; i < (ll)size(); i++) { (*this)[i] = -(*this)[i]; }
        for(ll i = 0; i < (ll)r.size(); i++) { (*this)[i] += r[i]; }
      }
    }
    return this->normalize();
  }
  lll &operator*=(ll r) {
    if((sign == 1 && r >= 0) || (sign == -1 && r < 0)) { sign = 1; }
    else { sign = -1; }
    if(r < 0) { r = -r; }
    for(ll i = 0; i < (ll)size(); i++) { (*this)[i] *= r; }
    return this->normalize();
  }
  lll &operator*=(const lll &r) {
    ll tx = size() - 1, ty = r.size() - 1;
    for(tx = size() - 1; tx >= 0; --tx) {
      if((*this)[tx] > 0) { break; }
    }
    for(ty = r.size() - 1; ty >= 0; --ty) {
      if(r[ty] > 0) { break; }
    }
    lll res(0);
    res.resize(tx + ty + 2);
    if(sign == r.sign) { res.sign = 1; }
    else { res.sign = -1; }
    for(ll i = 0; i <= tx; i++) {
      for(ll j = 0; j <= ty && i + j < res.size() - 1; j++) {
        ll val = (*this)[i] * r[j] + res[i + j];
        res[i + j + 1] += val / lll::BASE;
        res[i + j] = val % lll::BASE;
      }
    }
    return (*this) = res.normalize();
  }
  friend lll POW(const lll &a, ll n) {
    lll r(1), b = a;
    while(n > 0) {
      if(n & 1) { r = r * b; }
      b = b * b;
      n >>= 1;
    }
    return r;
  }
  lll operator+(const lll &r) const { return lll(*this) += r; }
  lll operator-(const lll &r) const { return lll(*this) -= r; }
  lll operator*(ll r) const { return lll(*this) *= r; }
  lll operator*(const lll &r) const { return lll(*this) *= r; }
  lll &operator/=(ll r) {
    if(r < 0) { sign *= -1, r = -r; }
    ll c = 0, t = 0;
    for(ll i = size() - 1; i >= 0; i--) {
      t = lll::BASE * c + (*this)[i];
      (*this)[i] = t / r;
      c = t % r;
    }
    this->normalize();
    return (*this);
  }
  ll operator%=(ll r) {
    if(r < 0) { sign *= -1, r = -r; }
    ll c = 0, t = 0;
    for(ll i = size() - 1; i >= 0; i--) {
      t = lll::BASE * c + (*this)[i];
      (*this)[i] = t / r;
      c = t % r;
    }
    return c;
  }
  lll operator/(ll r) const { return lll(*this) /= r; }
  ll operator%(ll r) const { return lll(*this) %= r; }
  friend pair<lll, lll> divmod(const lll &a, const lll &r) {
    lll zero = 0, s = 0, t = 0;
    if(abs(a) < abs(r)) { return {zero, a}; }
    lll ar = abs(r);
    s.resize(a.size()), t.resize(r.size());
    ll tx = a.size() - 1;
    for(; tx >= 0; --tx) {
      if(a[tx] > 0) { break; }
    }
    for(ll i = tx; i >= 0; i--) {
      t = t * lll::BASE + a[i];
      ll lo = 0, hi = lll::BASE;
      if(t >= ar) {
        while(hi - lo > 1) {
          ll mid = (hi + lo) / 2;
          if(ar * mid > t) hi = mid;
          else lo = mid;
        }
        t -= ar * lo;
      }
      s[i] = lo;
    }
    if(a.sign == r.sign) { s.sign = 1, t.sign = 1; }
    else { s.sign = -1, t.sign = 1; }
    return make_pair(s.normalize(), t.normalize());
  }
  lll operator/(const lll &r) const { return divmod((*this), r).first; }
  lll operator%(const lll &r) const { return divmod((*this), r).second; }
  lll &operator/=(const lll &r) { return (*this) = (*this) / r; }
  lll &operator%=(const lll &r) { return (*this) = (*this) % r; }
  friend bool operator<(const lll &x, const lll &y) {
    if(x.sign < y.sign) { return true; }
    else if(x.sign > y.sign) { return false; }
    else {
      ll tx = x.size() - 1, ty = y.size() - 1;
      for(tx = x.size() - 1; tx >= 0; --tx) {
        if(x[tx] > 0) { break; }
      }
      for(ty = y.size() - 1; ty >= 0; --ty) {
        if(y[ty] > 0) { break; }
      }
      if(tx < ty) { return true; }
      else if(tx > ty) { return false; }
      else if(x.sign == 1) {
        for(ll i = tx; i >= 0; i--) {
          if(x[i] != y[i]) { return x[i] < y[i]; }
        }
        return false;
      }
      else {
        for(ll i = tx; i >= 0; i--) {
          if(x[i] != y[i]) { return x[i] > y[i]; }
        }
        return false;
      }
    }
  }
  friend bool operator>(const lll &x, const lll &y) { return y < x; }
  friend bool operator<=(const lll &x, const lll &y) { return !(x > y); }
  friend bool operator>=(const lll &x, const lll &y) { return !(x < y); }
  friend bool operator==(const lll &x, const lll &y) {
    if(x.sign != y.sign) { return 0; }
    ll tx = (ll)x.size() - 1, ty = (ll)y.size() - 1;
    for(tx = x.size() - 1; tx >= 0; --tx) {
      if(x[tx] > 0) { break; }
    }
    for(ty = y.size() - 1; ty >= 0; --ty) {
      if(y[ty] > 0) { break; }
    }
    if(tx != ty) { return false; }
    for(ll i = tx; i >= 0; i--) {
      if(x[i] != y[i]) { return false; }
    }
    return true;
  }
  friend bool operator!=(const lll &x, const lll &y) { return !(x == y); }
};

lll tolll(const string &is) {
  string s = is;
  if(s[0] == '-') { s = s.substr(1); }
  while(s.size() % lll::BASE_D != 0) s = "0" + s;
  ll N = s.size();
  lll res(N / lll::BASE_D, 0);
  for(ll i = 0; i < (ll)s.size(); i++) {
    res[(N - i - 1) / lll::BASE_D] *= 10;
    res[(N - i - 1) / lll::BASE_D] += s[i] - '0';
  }
  if(is[0] == '-') { res.sign = -1; }
  return res;
}
string tostr(const lll &r) {
  stringstream ss;
  if(r.sign == -1) { ss << '-'; }
  ll d = r.size() - 1;
  for(; d >= 0; --d) {
    if(r[d] > 0) { break; }
  }
  if(d == -1) { ss << 0; }
  else { ss << r[d]; }
  for(ll i = d - 1; i >= 0; i--) {
    ss.width(lll::BASE_D);
    ss.fill('0');
    ss << r[i];
  }
  return ss.str();
}

istream &operator>>(istream &is, lll &x) {
  string s;
  is >> s;
  x = tolll(s);
  return is;
}
ostream &operator<<(ostream &os, const lll &x) {
  if(x.sign == -1) { os << '-'; }
  ll d = x.size() - 1;
  for(d = x.size() - 1; d >= 0; --d) {
    if(x[d] > 0) { break; }
  }
  if(d == -1) { os << 0; }
  else { os << x[d]; }
  for(ll i = d - 1; i >= 0; i--) {
    os.width(lll::BASE_D);
    os.fill('0');
    os << x[i];
  }
  return os;
}

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

  string S;
  cin >> S;

  ranges::sort(S);
  ll g = 0;
  for(ll i = 0; i < (int)S.size() - 1; i++) {
    g = gcd(g, 9 * (S[i + 1] - S[i]));
  }

  if(!g) { cout << S << "\n"; }
  else { cout << gcd(tolll(S) % 22680, g) << "\n"; }
}

yukicoder

結果

テストケース

ソースコード