結果
問題 | No.377 背景パターン |
ユーザー | Min_25 |
提出日時 | 2016-07-10 11:27:12 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,522 bytes |
コンパイル時間 | 1,468 ms |
コンパイル使用メモリ | 87,348 KB |
最終ジャッジ日時 | 2024-04-21 11:31:21 |
合計ジャッジ時間 | 1,912 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/string:43, from /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/bits/locale_classes.h:40, from /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/bits/ios_base.h:41, from /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/ios:44, from /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/ostream:40, from /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/iostream:41, from main.cpp:11: /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/bits/allocator.h: In destructor 'std::_Vector_base<std::pair<int, int>, std::allocator<std::pair<int, int> > >::_Vector_impl::~_Vector_impl()': /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to 'always_inline' 'std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::pair<int, int>]': target specific option mismatch 184 | ~allocator() _GLIBCXX_NOTHROW { } | ^ In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/vector:66, from main.cpp:12: /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/bits/stl_vector.h:133:14: note: called from here 133 | struct _Vector_impl | ^~~~~~~~~~~~
ソースコード
#pragma GCC optimize ("O3") #pragma GCC target ("avx") // yukicoder // #pragma GCC target ("sse4.2") // SPOJ, codechef #include <cstdio> #include <cassert> #include <cmath> #include <cstring> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <set> #include <functional> #include <tuple> #define _rep(_1, _2, _3, _4, name, ...) name #define rep2(i, n) rep3(i, 0, n) #define rep3(i, a, b) rep4(i, a, b, 1) #define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c)) #define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__) using namespace std; using i64 = long long; using u8 = unsigned char; using u32 = unsigned; using u64 = unsigned long long; using f80 = long double; using factor_t = pair<int, int>; vector<factor_t> factors(int n) { vector<factor_t> ret; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { int e = 0; while (n % i == 0) n /= i, e += 1; ret.push_back({i, e}); } } if (n) ret.push_back({n, 1}); return ret; } using P = pair<int, int>; vector<P> div_tot(int n) { vector<P> ret; ret.push_back({1, 1}); for (auto pp : factors(n)) { int p, e; tie(p, e) = pp; int size = ret.size(); rep(i, size * e) { ret.push_back({ret[i].first * p, ret[i].second * (p - (i < size))}); } } return ret; } const int MOD = 1e9 + 7; const int S = 1 << 15; int pows[2][S]; void init_pow(int K) { rep(i, 2) { int q = 1; rep(j, S) { pows[i][j] = q; q = u64(q) * K % MOD; } K = q; } } int pow_mod(int e) { return u64(pows[0][e & (S - 1)]) * pows[1][e >> 15] % MOD; } int pow_mod(int b, int e) { int ret = 1; for (; e; e >>= 1, b = u64(b) * b % MOD) { if (e & 1) ret = u64(ret) * b % MOD; } return ret; } void solve() { int H, W, K; while (~scanf("%d %d %d", &H, &W, &K)) { init_pow(K); auto div1 = div_tot(H); auto div2 = div_tot(W); u64 ans = 0; for (auto dt1 : div1) { int d1, t1; tie(d1, t1) = dt1; int g1 = __gcd(d1, W); u64 M = u64(H) * W / d1; for (auto dt2 : div2) { int d2, t2; tie(d2, t2) = dt2; int g2 = __gcd(d2, g1); ans += u64(t1) * t2 % MOD * pow_mod(M / d2 * g2 % (MOD - 1)) % MOD; } } ans = ans % MOD * pow_mod(u64(H) * W % MOD, MOD - 2) % MOD; printf("%llu\n", ans % MOD); } } int main() { clock_t beg = clock(); solve(); clock_t end = clock(); fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC); return 0; }