結果
問題 | No.377 背景パターン |
ユーザー |
|
提出日時 | 2016-06-05 00:25:49 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 599 ms / 5,000 ms |
コード長 | 1,471 bytes |
コンパイル時間 | 1,707 ms |
コンパイル使用メモリ | 174,468 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-08 13:17:24 |
合計ジャッジ時間 | 3,730 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long mod = 1e9 + 7;long long lcm(long long x, long long y) {return x / __gcd(x, y) * y;}long long modpow(long long a, long long b, long long mod) {long long result = 1;for (; b > 0; (a *= a) %= mod, b /= 2) if (b % 2 == 1) (result *= a) %= mod;return result;}long long modinv(long long a, long long mod) {return modpow(a, mod - 2, mod);}vector<long long> divisors(long long n) {vector<long long> ret;for (long long i = 1; i * i <= n; i++) if (n % i == 0) {ret.push_back(i);if (i != n / i) ret.push_back(n / i);}sort(ret.begin(), ret.end());return ret;}map<long long, long long> gcd_num(long long n) {map<long long, long long> sum;auto ds = divisors(n);for (int d : ds) {long long l = d;long long r = n / d * d;long long num = (r - l) / d + 1;sum[d] = num % mod;}for (int i = ds.size() - 1; i >= 0; i--) {for (int j = 0; j < i; j++) {if (ds[i] % ds[j] == 0) (sum[ds[j]] += mod - sum[ds[i]]) %= mod;}}return sum;}int main() {long long h, w, K;cin >> h >> w >> K;auto hh = gcd_num(h);auto ww = gcd_num(w);long long ans = 0;for (auto v1 : hh) {for (auto v2 : ww) {long long group = lcm(h / v1.first, w / v2.first);long long orbit = h * w / group;ans += modpow(K, orbit, mod) * (v1.second * v2.second % mod) % mod;ans %= mod;}}ans *= modinv(h * w % mod, mod);ans %= mod;cout << ans << endl;}