結果
| 問題 | No.886 Direct |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2020-12-31 05:06:12 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 243 ms / 4,000 ms |
| コード長 | 10,514 bytes |
| コンパイル時間 | 2,066 ms |
| コンパイル使用メモリ | 204,092 KB |
| 最終ジャッジ日時 | 2025-01-17 08:46:05 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;using i128 = __int128_t;using u128 = __uint128_t;using f64 = double;using f80 = long double;using f128 = __float128;using uint = unsigned int;using ll = long long;using ull = unsigned long long;using ld = long double;using LL = __int128_t;using ULL = __uint128_t;template<typename T> using max_heap = std::priority_queue<T>;template<typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;std::vector<int> factor_table(const int sup){std::vector<int> fact(sup);std::iota(fact.begin(), fact.end(), 0);for (int i = 2; i < sup; i++) {if (fact[i] != i) { continue; }for (int j = i + i; j < sup; j += i) { fact[j] = i; }}return fact;}std::vector<i32> prime_enumerate(const i32 sup){const auto ftable = factor_table(sup);std::vector<i32> ps;for (i32 p = 2; p < sup; p++) {if (ftable[p] == p) { ps.push_back(p); }}return ps;}template<typename T>std::vector<T> divisors_moebius(const std::vector<T>& xs, const bool subset){const int N = (int)xs.size();auto ys = xs;for (const i32 p : prime_enumerate(N)) {if (subset) {for (i32 i = (N - 1) / p; i >= 1; i--) { ys[i * p] -= ys[i]; }} else {for (i32 i = 1; i * p < N; i++) { ys[i] -= ys[i * p]; }}}return ys;}template<typename T>std::vector<T> divisors_zeta(const std::vector<T>& xs, const bool subset){const int N = (int)xs.size();auto ys = xs;for (const i32 p : prime_enumerate(N)) {if (subset) {for (i32 i = 1; i * p < N; i++) { ys[i * p] += ys[i]; }} else {for (i32 i = (N - 1) / p; i >= 1; i--) { ys[i] += ys[i * p]; }}}return ys;}template<typename T>std::vector<T> gcd_convolute(const std::vector<T>& f, const std::vector<T>& g){const int N = (int)std::min(f.size(), g.size());auto F = divisors_zeta(f, false), G = divisors_zeta(g, false);F.resize(N), G.resize(N);for (int i = 0; i < N; i++) { F[i] *= G[i]; }return divisors_moebius(F, false);}struct modinfo{void set_mod(const uint nmod) { mod = nmod; }uint mod, root, max2p;};template<const modinfo& info>class modint{public:static constexpr const uint& mod = info.mod;static constexpr const uint& root = info.root;static constexpr const uint& max2p = info.max2p;constexpr modint() : m_val{0} {}constexpr modint(const ll v) : m_val{normll(v)} {}constexpr void set_raw(const uint v) { m_val = v; }constexpr modint operator-() const { return modint{0} - (*this); }constexpr modint& operator+=(const modint& m) { return m_val = norm(m_val + m()), *this; }constexpr modint& operator-=(const modint& m) { return m_val = norm(m_val + mod - m()), *this; }constexpr modint& operator*=(const modint& m) { return m_val = normll((ll)m_val * (ll)m() % (ll)mod), *this; }constexpr modint& operator/=(const modint& m) { return *this *= m.inv(); }constexpr modint operator+(const modint& m) const { return modint{*this} += m; }constexpr modint operator-(const modint& m) const { return modint{*this} -= m; }constexpr modint operator*(const modint& m) const { return modint{*this} *= m; }constexpr modint operator/(const modint& m) const { return modint{*this} /= m; }constexpr bool operator==(const modint& m) const { return m_val == m(); }constexpr bool operator!=(const modint& m) const { return not(*this == m); }friend std::istream& operator>>(std::istream& is, modint& m){ll v;return is >> v, m = v, is;}friend std::ostream& operator<<(std::ostream& os, const modint& m) { return os << m(); }constexpr uint get() const { return m_val; }constexpr uint operator()() const { return m_val; }constexpr modint pow(ull n) const{modint ans = 1;for (modint x = *this; n > 0; n >>= 1, x *= x) {if (n & 1ULL) { ans *= x; }}return ans;}constexpr modint inv() const { return pow(mod - 2); }static modint sinv(const uint n){static std::vector<modint> is{1, 1};for (uint i = (uint)is.size(); i <= n; i++) { is.push_back(-is[mod % i] * (mod / i)); }return is[n];}static modint fact(const uint n){static std::vector<modint> fs{1, 1};for (uint i = (uint)fs.size(); i <= n; i++) { fs.push_back(fs.back() * i); }return fs[n];}static modint ifact(const uint n){static std::vector<modint> ifs{1, 1};for (uint i = (uint)ifs.size(); i <= n; i++) { ifs.push_back(ifs.back() * sinv(i)); }return ifs[n];}static modint comb(const int n, const int k) { return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k) * ifact(k); }private:static constexpr uint norm(const uint x) { return x < mod ? x : x - mod; }static constexpr uint normll(const ll x) { return norm(uint(x % (ll)mod + (ll)mod)); }uint m_val;};constexpr modinfo modinfo_1000000007 = {1000000007, 5, 1};constexpr modinfo modinfo_998244353 = {998244353, 3, 23};using modint_1000000007 = modint<modinfo_1000000007>;using modint_998244353 = modint<modinfo_998244353>;class printer{public:printer(){for (int i = 0; i < 10000; i++) {for (int j = i, t = 3; t >= 0; t--, j /= 10) { m_dict[i * 4 + t] = (j % 10) + '0'; }}}~printer() { flush(); }template<typename... Args> int ln(const Args&... args) { return dump(args...), put_char('\n'), 0; }template<typename... Args> int el(const Args&... args) { return dump(args...), put_char('\n'), flush(), 0; }private:using ll = long long;using ull = unsigned long long;static constexpr ull TEN(const int d) { return d == 0 ? 1ULL : TEN(d - 1) * 10ULL; }void flush() { fwrite(m_memory, 1, m_tail, stdout), m_tail = 0; }void put_char(const char c) { m_memory[m_tail++] = c; }static constexpr int dn(const ull x){return x < TEN(10)? x < TEN(5)? x < TEN(2)? x < TEN(1) ? 1 : 2: x < TEN(3) ? 3 : x < TEN(4) ? 4 : 5: x < TEN(7)? x < TEN(6) ? 6 : 7: x < TEN(8) ? 8 : x < TEN(9) ? 9 : 10: x < TEN(14)? x < TEN(12)? x < TEN(11) ? 11 : 12: x < TEN(13) ? 13 : 14: x < TEN(16)? x < TEN(15) ? 15 : 16: x < TEN(17) ? 17 : x < TEN(18) ? 18 : 19;}void dump(const char* s) { dump(std::string{s}); }void dump(const std::string& s){for (const char c : s) { put_char(c); }}template<typename T>void dump(T v){if (C - m_tail < 50) { flush(); }if (v < 0) { put_char('-'), v = -v; }const auto d = dn(v);int i = d - 4;for (i = d - 4; i >= 0; i -= 4, v /= 10000) { memcpy(m_memory + m_tail + i, m_dict + (v % 10000) * 4, 4); }memcpy(m_memory + m_tail, m_dict + v * 4 - i, i + 4);m_tail += d;}template<typename T>void dump(const std::vector<T>& vs){for (int i = 0; i < (int)vs.size(); i++) {if (i > 0) { put_char(' '); }dump(vs[i]);}}template<typename T>void dump(const std::vector<std::vector<T>>& vss){for (int i = 0; i < (int)vss.size(); i++) {if (i > 0) { put_char('\n'); }dump(vss[i]);}}template<typename T, typename... Args> void dump(const T& v, const Args&... args) { return dump(v), put_char(' '), dump(args...), void(0); }static constexpr int C = 1 << 18;int m_tail = 0;char m_memory[C];char m_dict[10000 * 4];} out;class scanner{public:scanner() {}template<typename T>T val(){if (m_tail - m_head < 40) { disk_read(); }char c = get_char();const bool neg = (c == '-');if (neg) { c = get_char(); }T ans = 0;while (c >= '0') {ans = ans * T{10} + (c - '0');c = get_char();}return (neg ? -ans : ans);}template<typename T> T val(const T offset) { return val<T>() - offset; }template<typename T> std::vector<T> vec(const int n){return make_v<T>(n, [this]() { return val<T>(); });}template<typename T> std::vector<T> vec(const int n, const T offset){return make_v<T>(n, [this, offset]() { return val<T>(offset); });}template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1){return make_v<std::vector<T>>(n0, [this, n1]() { return vec<T>(n1); });}template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1, const T offset){return make_v<std::vector<T>>(n0, [this, n1, offset]() { return vec<T>(n1, offset); });}template<typename... Args> auto tup() { return std::tuple<std::decay_t<Args>...>{val<Args>()...}; }template<typename... Args> auto tup(const Args&... offsets) { return std::tuple<std::decay_t<Args>...>{val<Args>(offsets)...}; }private:template<typename T, typename F>std::vector<T> make_v(const int n, F f){std::vector<T> ans;for (int i = 0; i < n; i++) { ans.push_back(f()); }return ans;}char get_char() { return m_memory[m_head++]; }void disk_read(){std::copy(m_memory + m_head, m_memory + m_tail, m_memory);m_tail -= m_head, m_head = 0;m_tail += fread(m_memory + m_tail, 1, C - m_tail, stdin);}static constexpr int C = 1 << 18;int m_head = 0, m_tail = 0;char m_memory[C];} in;int main(){using mint = modint_1000000007;const auto [H, W] = in.tup<int, int>();mint ans = mint(H) * (W - 1) + mint(H - 1) * W;std::vector<mint> as(H), bs(W);for (int i = 1; i < H; i++) { as[i] = H - i; }for (int i = 1; i < W; i++) { bs[i] = W - i; }const auto cs = gcd_convolute(as, bs);ans += (cs.size() < 2 ? mint{0} : cs[1]) * 2;out.ln(ans());return 0;}