結果
問題 | No.377 背景パターン |
ユーザー |
![]() |
提出日時 | 2016-07-10 11:51:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 5,000 ms |
コード長 | 3,023 bytes |
コンパイル時間 | 1,366 ms |
コンパイル使用メモリ | 100,620 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-14 19:46:51 |
合計ジャッジ時間 | 2,146 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 14 |
ソースコード
#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(const vector<factor_t>& fac) {vector<P> ret;ret.push_back({1, 1});for (auto pp : fac) {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;}vector<P> div_offsets(const vector<factor_t>& fac) {vector<P> ret(1, {0, 1});for (auto pp : fac) {int size = ret.size();rep(i, size * pp.second) {ret.push_back({size, pp.first});}}return ret;}void solve() {int H, W, K;while (~scanf("%d %d %d", &H, &W, &K)) {init_pow(K);auto f1 = factors(H); auto div1 = div_tot(f1);auto f2 = factors(W); auto div2 = div_tot(f2);auto div2_ofs = div_offsets(f2);vector<int> gcd_tab(div2.size());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;gcd_tab[0] = 1;rep(i, div2.size()) {int d2, t2; tie(d2, t2) = div2[i];int ofs, p; tie(ofs, p) = div2_ofs[i];int g = gcd_tab[i - ofs];if (g1 % (g * p) == 0) g *= p;ans += u64(t1) * t2 % MOD * pow_mod(M / d2 * g % (MOD - 1)) % MOD;gcd_tab[i] = g;}}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;}