結果
問題 | No.886 Direct |
ユーザー | hasegawa1 |
提出日時 | 2021-08-24 00:44:00 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,245 bytes |
コンパイル時間 | 1,058 ms |
コンパイル使用メモリ | 92,244 KB |
実行使用メモリ | 56,880 KB |
最終ジャッジ日時 | 2024-04-25 21:29:45 |
合計ジャッジ時間 | 9,902 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 49 ms
18,940 KB |
testcase_01 | AC | 49 ms
19,008 KB |
testcase_02 | AC | 47 ms
18,924 KB |
testcase_03 | AC | 47 ms
19,176 KB |
testcase_04 | AC | 47 ms
18,900 KB |
testcase_05 | AC | 43 ms
18,836 KB |
testcase_06 | AC | 46 ms
18,856 KB |
testcase_07 | AC | 47 ms
18,944 KB |
testcase_08 | AC | 44 ms
18,996 KB |
testcase_09 | AC | 50 ms
18,856 KB |
testcase_10 | AC | 46 ms
18,800 KB |
testcase_11 | AC | 46 ms
18,796 KB |
testcase_12 | AC | 46 ms
18,976 KB |
testcase_13 | AC | 51 ms
18,952 KB |
testcase_14 | AC | 48 ms
18,836 KB |
testcase_15 | AC | 47 ms
18,940 KB |
testcase_16 | AC | 45 ms
18,916 KB |
testcase_17 | AC | 45 ms
19,392 KB |
testcase_18 | AC | 47 ms
19,436 KB |
testcase_19 | AC | 46 ms
19,364 KB |
testcase_20 | AC | 51 ms
19,176 KB |
testcase_21 | AC | 46 ms
19,564 KB |
testcase_22 | AC | 46 ms
19,440 KB |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | RE | - |
testcase_32 | RE | - |
testcase_33 | RE | - |
testcase_34 | RE | - |
testcase_35 | RE | - |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <numeric> #include <cstdint> #include <cassert> #include "atcoder/modint" using namespace std; using mint = atcoder::modint1000000007; class Sieve { private: const int _n; std::vector<int> _max_prime_factor; std::vector<int> _euler_phi; public: explicit Sieve(int n = 2'000'000): _n(n+1), _max_prime_factor(_n), _euler_phi(_n) { iota(_euler_phi.begin(), _euler_phi.end(), 0); for(int i=2; i<_n; i++) { if(_max_prime_factor[i]) continue; for(int j=i; j<_n; j+=i) { _max_prime_factor[j] = i; _euler_phi[j] -= _euler_phi[j]/i; } } } bool is_prime(int64_t n) const { assert(n > 0); if(n < _n) return (_max_prime_factor[n] == n); return atcoder::internal::is_prime_constexpr(n); } std::vector<std::pair<int64_t,int64_t>> prime_factorize(int64_t n) const { assert(n > 0); std::vector<std::pair<int64_t,int64_t>> res; if(n < _n) { while(n > 1) { int64_t p = _max_prime_factor[n]; int64_t exp = 0; while(_max_prime_factor[n] == p) { n /= p; ++exp; } res.emplace_back(p, exp); } std::reverse(res.begin(), res.end()); } else { for(int64_t i=2; i*i<=n; i++) { if(n%i == 0) { int exp = 0; while(n%i == 0) { n /= i; ++exp; } res.emplace_back(i, exp); } } if(n != 1) res.emplace_back(n, 1); } return res; } std::vector<int64_t> divisors(int64_t n) const { assert(n > 0); std::vector<int64_t> res = {1}; for(const auto [p, exp]: prime_factorize(n)) { int sz = res.size(); for(int i=0; i<sz; i++) { int64_t now = res[i]; for(int j=0; j<exp; j++) { now *= p; res.emplace_back(now); } } } sort(res.begin(), res.end()); return res; } int64_t euler_phi(int64_t n) const { assert(n > 0); if(n < _n) return _euler_phi[n]; int64_t res = n; for(const auto [p, exp]: prime_factorize(n)) { res -= res/p; } return res; } template<typename T> std::vector<T> divisor_transform(std::vector<T> v) { int n = v.size(); assert(n <= _n); for(int i=2; i<n; i++) { if(is_prime(i)) { for(int j=1; i*j<n; j++) { v[j * i] += v[j]; } } } return v; } template<typename T> std::vector<T> inverse_divisor_transform(std::vector<T> v) { int n = v.size(); assert(n <= _n); for(int i=2; i<n; i++) { if(is_prime(i)) { for(int j=(n-1)/i; j>0; j--) { v[j * i] -= v[j]; } } } return v; } template<typename T> std::vector<T> multiple_transform(std::vector<T> v) { int n = v.size(); assert(n <= _n); for(int i=2; i<n; i++) { if(is_prime(i)) { for(int j=(n-1)/i; j>0; j--) { v[j] += v[j * i]; } } } return v; } template<typename T> std::vector<T> inverse_multiple_transform(std::vector<T> v) { int n = v.size(); assert(n <= _n); for(int i=2; i<n; i++) { if(is_prime(i)) { for(int j=1; i*j<n; j++) { v[j] -= v[j * i]; } } } return v; } template<typename T> std::vector<T> gcd_convolution(const std::vector<T> &a, const std::vector<T> &b) { assert(a.size() == b.size()); auto sum_a = multiple_transform(a); auto sum_b = multiple_transform(b); std::vector<T> sum_c; std::transform(sum_a.begin(), sum_a.end(), sum_b.begin(), std::back_inserter(sum_c), std::multiplies<T>()); return inverse_multiple_transform(sum_c); } template<typename T> std::vector<T> lcm_convolution(const std::vector<T> &a, const std::vector<T> &b) { assert(a.size() == b.size()); auto sum_a = divisor_transform(a); auto sum_b = divisor_transform(b); std::vector<T> sum_c; std::transform(sum_a.begin(), sum_a.end(), sum_b.begin(), std::back_inserter(sum_c), std::multiplies<T>()); return inverse_divisor_transform(sum_c); } }; int main(void) { cin.tie(nullptr); ios_base::sync_with_stdio(false); Sieve s; int H, W; cin >> H >> W; int M = max(H, W); vector<mint> h(M+1), w(M+1); for(int i=1; i<H; i++) { h[i] = H-i; } for(int i=1; i<W; i++) { w[i] = W-i; } mint ans = (H-1)*W + H*(W-1) + 2*s.gcd_convolution(h, w)[1]; cout << ans.val() << endl; }