結果
| 問題 | No.3028 No.9999 |
| ユーザー |
 Tatsu_mr
|
| 提出日時 | 2025-02-21 21:52:39 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 14,319 bytes |
| コンパイル時間 | 6,659 ms |
| コンパイル使用メモリ | 335,224 KB |
| 実行使用メモリ | 13,632 KB |
| 最終ジャッジ日時 | 2025-02-21 21:52:53 |
| 合計ジャッジ時間 | 12,257 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 5 TLE * 1 -- * 17 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/convolution>using namespace std;#define For(i, a, b) for(int i = (a); i < (b); i++)#define rep(i, n) For(i, 0, n)#define rFor(i, a, b) for(int i = (a); i >= (b); i--)#define ALL(v) (v).begin(), (v).end()#define rALL(v) (v).rbegin(), (v).rend()using lint = long long;using ld = long double;int INF = 2000000000;lint LINF = 1000000000000000000;struct SetupIo {SetupIo() {ios::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(15);}} setupio;namespace rklib {template <class T>std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {os << "[";for (auto d : v) os << d << ", ";return os << "]";}// a <- max(a, b)template <class T>bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}// a <- min(a, b)template <class T>bool chmin(T &a, const T &b) {if (a > b) {a = b;return true;}return false;}// if a < 0: a <- b// else: a <- min(a, b)template <class T>bool chmin_non_negative(T &a, const T &b) {if (a < 0 || a > b) {a = b;return true;}return false;}// floor(num / den)template <class T>T div_floor(T num, T den) {if (den < 0) num = -num, den = -den;return num >= 0 ? num / den : (num + 1) / den - 1;}// ceil(num / den)template <class T>T div_ceil(T num, T den) {if (den < 0) num = -num, den = -den;return num <= 0 ? num / den : (num - 1) / den + 1;}} // namespace rklibnamespace rklib {struct BigInt {public:BigInt() : BigInt(0) {}template <typename T, std::enable_if_t<std::is_integral<T>::value,std::nullptr_t> = nullptr>BigInt(T x) : BigInt(std::vector<T>(1, x)) {}template <typename T, std::enable_if_t<std::is_integral<T>::value,std::nullptr_t> = nullptr>BigInt(std::vector<T> a) {while (a.size() >= 2 && a.back() == 0) a.pop_back();if (a.size() == 1 && a[0] == 0) {sgn = 0;v = {0};return;}sgn = (a.back() > 0 ? 1 : -1);if (sgn < 0) {std::transform(a.begin(), a.end(), a.begin(),[](T x) { return -x; });}v = normalize(a);}BigInt(std::string s) : sgn(1) {if (s[0] == '-') {s.erase(s.begin());sgn = -1;}if (s == "0") {sgn = 0;v = {0};return;}for (int r = int(s.size()), l = std::max(0, r - log10_base); r > 0;r = l, l = std::max(0, r - log10_base)) {int tmp = 0;for (int i = l; i < r; ++i) {tmp = tmp * 10 + (s[i] - '0');}v.push_back(tmp);}}BigInt& operator+=(const BigInt& rhs) {int r_sgn = rhs.sgn;if (r_sgn == 0) return *this;if (sgn == 0) return *this = rhs;if (v.size() < rhs.v.size()) v.resize(rhs.v.size(), 0);for (size_t i = 0; i < rhs.v.size(); i++) {if (sgn == r_sgn)v[i] += rhs.v[i];elsev[i] -= rhs.v[i];}normalize();return *this;}BigInt& operator-=(const BigInt& rhs) {int r_sgn = rhs.sgn;if (r_sgn == 0) return *this;if (sgn == 0) return *this = -rhs;if (v.size() < rhs.v.size()) v.resize(rhs.v.size(), 0);for (size_t i = 0; i < rhs.v.size(); i++) {if (sgn == r_sgn)v[i] -= rhs.v[i];elsev[i] += rhs.v[i];}normalize();return *this;}BigInt& operator*=(const BigInt& rhs) {int r_sgn = rhs.sgn;if (sgn == 0) return *this;if (r_sgn == 0) return *this = rhs;int res_sgn = sgn * r_sgn;if (int(std::min(v.size(), rhs.v.size())) <= naive_mul_threshold) {v = multiply_naive(v, rhs.v);} else if (std::max(v.size(), rhs.v.size()) > karatsuba_mul_threshold &&v.size() + rhs.v.size() - 1 <= (1 << 24)) {v = multiply_ntt(v, rhs.v);} else {std::vector<long long> a(v.size()), b(rhs.v.size());for (size_t i = 0; i < a.size(); i++) {a[i] = (long long)v[i];}for (size_t i = 0; i < b.size(); i++) {b[i] = (long long)rhs.v[i];}int sz = 1;while (sz < int(a.size()) || sz < int(b.size())) sz *= 2;a.resize(sz, 0);b.resize(sz, 0);this->v = normalize(multiply_karatsuba(a, b));}this->sgn = res_sgn;return *this;}BigInt& operator/=(const BigInt& rhs) {int r_sgn = rhs.sgn;assert(r_sgn != 0);if (sgn == 0) return *this;if (rhs == BigInt(1) || rhs == BigInt(-1)) {sgn *= r_sgn;return *this;}int res_sgn = sgn * r_sgn;(*this) = divide_newton_raphson(*this, rhs);this->sgn = (this->v.back() == 0 ? 0 : res_sgn);return *this;}BigInt& operator%=(const BigInt& rhs) {assert(rhs.sgn != 0);return *this = (*this) - (*this) / rhs * rhs;}friend BigInt operator+(const BigInt& lhs, const BigInt& rhs) {return BigInt(lhs) += rhs;}friend BigInt operator-(const BigInt& lhs, const BigInt& rhs) {return BigInt(lhs) -= rhs;}friend BigInt operator*(const BigInt& lhs, const BigInt& rhs) {return BigInt(lhs) *= rhs;}friend BigInt operator/(const BigInt& lhs, const BigInt& rhs) {return BigInt(lhs) /= rhs;}friend BigInt operator%(const BigInt& lhs, const BigInt& rhs) {return BigInt(lhs) %= rhs;}BigInt operator+() const { return *this; }BigInt operator-() const { return {-sgn, v}; }BigInt& operator++() { return *this += 1; }BigInt& operator--() { return *this -= 1; }friend bool operator==(const BigInt& lhs, const BigInt& rhs) {if (lhs.sgn != rhs.sgn || lhs.v.size() != rhs.v.size()) return false;for (size_t i = 0; i < lhs.v.size(); i++) {if (lhs.v[i] != rhs.v[i]) return false;}return true;}friend bool operator!=(const BigInt& lhs, const BigInt& rhs) {return !(lhs == rhs);}friend bool operator<(const BigInt& lhs, const BigInt& rhs) {int l_sgn = lhs.sgn, r_sgn = rhs.sgn;if (l_sgn < r_sgn) return true;if (l_sgn > r_sgn) return false;int nl = lhs.v.size(), nr = rhs.v.size();if (l_sgn * nl < r_sgn * nr) return true;if (l_sgn * nl > r_sgn * nr) return false;for (int i = nl - 1; i >= 0; i--) {if (l_sgn * lhs.v[i] < r_sgn * rhs.v[i]) return true;if (l_sgn * lhs.v[i] > r_sgn * rhs.v[i]) return false;}return false;}friend bool operator>(const BigInt& lhs, const BigInt& rhs) {return rhs < lhs;}friend bool operator<=(const BigInt& lhs, const BigInt& rhs) {return !(lhs > rhs);}friend bool operator>=(const BigInt& lhs, const BigInt& rhs) {return rhs <= lhs;}friend std::istream& operator>>(std::istream& is, BigInt& rhs) {std::string s;is >> s;rhs = BigInt(s);return is;}friend std::ostream& operator<<(std::ostream& os, const BigInt& rhs) {if (rhs.sgn < 0) os << "-";for (int i = int(rhs.v.size()) - 1; i >= 0; i--) {if (i == int(rhs.v.size()) - 1) {os << rhs.v[i];} else {os << std::to_string(rhs.v[i] + base).substr(1, log10_base);}}return os;}operator double() const {double res = 0;for (int i = v.size() - 1; i >= 0; i--) {res = res * base + v[i];}res *= sgn;return res;}operator long double() const {long double res = 0;for (int i = v.size() - 1; i >= 0; i--) {res = res * base + v[i];}res *= sgn;return res;}private:static constexpr int base = 10000, log10_base = 4;static constexpr int naive_mul_threshold = 75,karatsuba_mul_threshold = 4000;int sgn;std::vector<int> v;BigInt(int sgn, std::vector<int> v) : sgn(sgn), v(v) {}void normalize() {while (v.size() >= 2 && v.back() == 0) v.pop_back();if (v.back() < 0) {sgn = -sgn;std::transform(v.begin(), v.end(), v.begin(),[](int x) { return -x; });}int carry = 0;for (size_t i = 0; i < v.size(); i++) {v[i] += carry;if (0 <= v[i] && v[i] < base) {carry = 0;continue;}carry = div_floor(v[i], base);v[i] -= carry * base;}while (carry > 0) {v.push_back(carry % base);carry /= base;}while (v.size() >= 2 && v.back() == 0) v.pop_back();if (v.size() == 1 && v[0] == 0) sgn = 0;}template <class T>static std::vector<int> normalize(const std::vector<T>& c) {std::vector<int> res(c.size());T carry = 0;for (size_t i = 0; i < c.size(); i++) {T tmp = c[i];tmp += carry;if (0 <= tmp && tmp < T(base)) {carry = 0;res[i] = int(tmp);continue;}carry = div_floor(tmp, T(base));res[i] = int(tmp - carry * base);}while (carry > 0) {res.push_back(int(carry % base));carry /= base;}while (res.size() >= 2 && res.back() == 0) res.pop_back();return res;}static std::vector<int> multiply_naive(const std::vector<int>& a,const std::vector<int>& b) {std::vector<long long> c(a.size() + b.size() - 1, 0);for (size_t i = 0; i < a.size(); i++) {for (size_t j = 0; j < b.size(); j++) {c[i + j] += a[i] * b[j];}}return normalize(c);}static std::vector<int> multiply_ntt(const std::vector<int>& a,const std::vector<int>& b) {std::vector<long long> al(a.size()), bl(b.size());for (size_t i = 0; i < a.size(); i++) {al[i] = (long long)a[i];}for (size_t i = 0; i < b.size(); i++) {bl[i] = (long long)b[i];}std::vector<long long> c = atcoder::convolution_ll(al, bl);return normalize(c);}static std::vector<long long> multiply_karatsuba(std::vector<long long> a,std::vector<long long> b) {int na = a.size(), nb = b.size();if (std::min(na, nb) <= naive_mul_threshold) {std::vector<long long> res(a.size() + b.size() - 1, 0);for (size_t i = 0; i < a.size(); i++) {for (size_t j = 0; j < b.size(); j++) {res[i + j] += a[i] * b[j];}}return res;}int n = std::max(na, nb);if (na < n) a.resize(n, 0);if (nb < n) b.resize(n, 0);int k = n / 2;std::vector<long long> x(std::vector<long long>(a.begin() + k, a.end()));std::vector<long long> y(std::vector<long long>(a.begin(), a.begin() + k));std::vector<long long> z(std::vector<long long>(b.begin() + k, b.end()));std::vector<long long> w(std::vector<long long>(b.begin(), b.begin() + k));std::vector<long long> xz = multiply_karatsuba(x, z);std::vector<long long> yw = multiply_karatsuba(y, w);for (int i = 0; i < k; i++) {x[i] += y[i];z[i] += w[i];}std::vector<long long> t = multiply_karatsuba(x, z);for (size_t i = 0; i < xz.size(); i++) {t[i] -= xz[i] + yw[i];}a = std::vector<long long>(2 * k, 0);a.insert(a.end(), xz.begin(), xz.end());b = std::vector<long long>(k, 0);b.insert(b.end(), t.begin(), t.end());for (size_t i = 0; i < b.size(); i++) {a[i] += b[i];}for (size_t i = 0; i < yw.size(); i++) {a[i] += yw[i];}return a;}static void shift_r(BigInt& a, size_t len) {if (a == BigInt(0)) return;if (a.v.size() <= len) {a = 0;return;}a.v.erase(a.v.begin(), a.v.begin() + len);}static BigInt divide_newton_raphson(BigInt a, BigInt b) {a.sgn = b.sgn = 1;if (a < b) return 0;size_t len = a.v.size() + 2;BigInt x = base * base, prv = x;while (true) {BigInt tmp = x * x * b;shift_r(tmp, len);x += x;x -= tmp;if (x.v.size() > len) shift_r(x, x.v.size() - len);if ((x - prv).v.size() <= 1) break;prv = x;}BigInt res = a * x;res.v.erase(res.v.begin(), res.v.begin() + len);if (res * b + b <= a) ++res;return res;}};} // namespace rklibusing namespace rklib;int main() {lint n;cin >> n;string str = to_string(n);BigInt N(str);for (string s = "9"; ; s += "9") {if (s.size() <= 18) {lint x = stoll(s);if (x % n == 0) {cout << s.size() << "\n";return 0;}} else {BigInt M(s);BigInt R = N % M;BigInt r("0");if (R == r) {cout << s.size() << "\n";return 0;}}}}