結果
| 問題 | No.1632 Sorting Integers (GCD of M) |
| ユーザー |
 tokusakurai
|
| 提出日時 | 2021-07-30 22:11:36 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 6,589 bytes |
| コンパイル時間 | 2,097 ms |
| コンパイル使用メモリ | 205,036 KB |
| 最終ジャッジ日時 | 2025-01-23 11:54:26 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 59 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for(int i = 0; i < n; i++)#define rep2(i, x, n) for(int i = x; i <= n; i++)#define rep3(i, x, n) for(int i = x; i >= n; i--)#define each(e, v) for(auto &e: v)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;const int MOD = 1000000007;//const int MOD = 998244353;const int inf = (1<<30)-1;const ll INF = (1LL<<60)-1;template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};struct io_setup{io_setup(){ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;template<int mod>struct Mod_Int{int x;Mod_Int() : x(0) {}Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}Mod_Int &operator += (const Mod_Int &p){if((x += p.x) >= mod) x -= mod;return *this;}Mod_Int &operator -= (const Mod_Int &p){if((x += mod - p.x) >= mod) x -= mod;return *this;}Mod_Int &operator *= (const Mod_Int &p){x = (int) (1LL * x * p.x % mod);return *this;}Mod_Int &operator /= (const Mod_Int &p){*this *= p.inverse();return *this;}Mod_Int &operator ++ () {return *this += Mod_Int(1);}Mod_Int operator ++ (int){Mod_Int tmp = *this;++*this;return tmp;}Mod_Int &operator -- () {return *this -= Mod_Int(1);}Mod_Int operator -- (int){Mod_Int tmp = *this;--*this;return tmp;}Mod_Int operator - () const {return Mod_Int(-x);}Mod_Int operator + (const Mod_Int &p) const {return Mod_Int(*this) += p;}Mod_Int operator - (const Mod_Int &p) const {return Mod_Int(*this) -= p;}Mod_Int operator * (const Mod_Int &p) const {return Mod_Int(*this) *= p;}Mod_Int operator / (const Mod_Int &p) const {return Mod_Int(*this) /= p;}bool operator == (const Mod_Int &p) const {return x == p.x;}bool operator != (const Mod_Int &p) const {return x != p.x;}Mod_Int inverse() const{assert(*this != Mod_Int(0));return pow(mod-2);}Mod_Int pow(long long k) const{Mod_Int now = *this, ret = 1;for(; k > 0; k >>= 1, now *= now){if(k&1) ret *= now;}return ret;}friend ostream &operator << (ostream &os, const Mod_Int &p){return os << p.x;}friend istream &operator >> (istream &is, Mod_Int &p){long long a;is >> a;p = Mod_Int<mod>(a);return is;}};using mint = Mod_Int<MOD>;struct Random_Number_Generator{mt19937_64 mt;Random_Number_Generator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}int64_t operator () (int64_t l, int64_t r){ //[l,r)で乱数発生uniform_int_distribution<int64_t> dist(l, r-1);return dist(mt);}int64_t operator () (int64_t r){ //[0,r)で乱数発生return (*this)(0, r);}};long long modpow(long long x, long long n, const int &m){long long ret = 1;for(; n > 0; n >>= 1, x *= x, x %= m){if(n&1) ret *= x, ret %= m;}return ret;}template<typename T>T Euler_Totient(T m){ //オイラーのφ関数(xとmが互いに素ならば、x^φ(m)≡1(mod m))T ret = m;for(T i = 2; i*i <= m; i++){if(m%i == 0) ret /= i, ret *= i-1;while(m%i == 0) m /= i;}if(m > 1) ret /= m, ret *= m-1;return ret;}int modlog(const int &x, long long y, const int &m){ //x^k=y(mod m)となる最小の非負整数k(xとmは互いに素)unordered_map<int, int> mp;int n = 0; long long now = 1;for(; n*n < m; n++){if(!mp.count(now)) mp[now] = n;now *= x, now %= m;}now = modpow(now, Euler_Totient(m)-1, m);for(int i = 0; i < n; i++){if(mp.count(y)) return n*i+mp[y];y *= now, y %= m;}return -1;}template<typename T>T order(T x, const T &m){ //x^k=1(mod m)となる最小の正整数k(xとmは互いに素)T n = Euler_Totient(m);vector<T> ds;for(T i = 1; i*i <= n; i++){if(n%i == 0) ds.push_back(i), ds.push_back(n/i);}sort(begin(ds), end(ds));for(auto &e: ds){if(modpow(x, e, m) == 1) return e;}return -1;}template<typename T>T primitive_root(const T &m){ //素数mの原始根vector<T> ds;for(T i = 1; i*i <= m-1; i++){if((m-1)%i == 0) ds.push_back(i), ds.push_back((m-1)/i);}sort(begin(ds), end(ds));Random_Number_Generator rnd;while(true){T r = rnd(1, m);for(auto &e: ds){if(e == m-1) return r;if(modpow(r, e, m) == 1) break;}}}int main(){ll N; cin >> N;vector<ll> c(10);rep2(i, 1, 9) cin >> c[i];vector<int> ids;int K = 0, G = 0;rep2(i, 1, 9){if(c[i] > 0){ids.eb(i);K++;G = gcd(G, i);}}if(K == 1){rep2(i, 1, 9){if(c[i] > 0){cout << (mint(10).pow(N)-1)*mint(i)/mint(9) << '\n';return 0;}}}ll ans = G;if(G > 1){each(e, ids) e /= G;rep2(i, 1, 9){if(c[i] > 0){c[i/G] = c[i];c[i] = 0;}}}ll T = 0;rep2(i, 1, 9){T += c[i]*i, T %= 9;}if(T == 0) ans *= 9;else if(T%3 == 0) ans *= 3;if(K >= 2){G = 0;rep(i, K-1){G = gcd(G, ids[i+1]-ids[i]);}if(G%3 == 0 && T == 0){int pre = 0;ll M = 0, A = N;rep2(i, 1, 9){if(c[i] > 0){ll X = modpow(10, A, 243);X += 242, X %= 243;X /= 9;M += X*(i-pre), M %= 27;A -= c[i], pre = i;}}if(M%27 == 0) ans *= 3;}}if(K == 2 && ids[1]-ids[0] == 7){ll M = modpow(10, N, 7);M += 6, M %= 7;M *= 4, M %= 7;if(M == 0) ans *= 7;}cout << ans << '\n';}