結果

問題 No.377 背景パターン
ユーザー pekempey
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0