結果
| 問題 | No.443 GCD of Permutation |
| ユーザー |
 kusaf_
|
| 提出日時 | 2024-09-01 10:48:40 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 28 |
ソースコード
#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"; }}