結果
問題 |
No.377 背景パターン
|
ユーザー |
![]() |
提出日時 | 2016-06-07 16:14:03 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,385 ms / 5,000 ms |
コード長 | 1,954 bytes |
コンパイル時間 | 1,169 ms |
コンパイル使用メモリ | 98,548 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-08 17:24:39 |
合計ジャッジ時間 | 4,908 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 14 |
ソースコード
#define _USE_MATH_DEFINES #include <algorithm> #include <cstdio> #include <functional> #include <iostream> #include <cfloat> #include <climits> #include <cstdlib> #include <cstring> #include <cmath> #include <map> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <string> #include <time.h> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> i_i; typedef pair<ll, int> ll_i; typedef pair<double, int> d_i; typedef pair<ll, ll> ll_ll; typedef pair<double, double> d_d; // struct edge { int u, v; ll w; }; int INF = INT_MAX; ll MOD = 1000000007; ll _MOD = 1000000009; double EPS = 1e-10; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } int pow_mod(ll x, ll n, int M) { ll ans = 1; for (; n; n>>=1) { if (n & 1) ans = ans * x % M; x = x * x % M; } return ans; } int inv_mod(int x, int p) { return pow_mod(x, p - 2, p); } vector<i_i> f(int N) { vector<int> ds; for (int x = 1; x * x <= N; x++) if (N % x == 0) { ds.push_back(x); if (x * x != N) ds.push_back(N / x); } sort(ds.begin(), ds.end()); int M = ds.size(); vector<int> a(M); for (int i = 0; i < M; i++) { int d = ds[i]; a[i] = d; vector<int> es; for (int x = 1; x * x <= d; x++) if (d % x == 0) { es.push_back(x); if (x * x != d) es.push_back(d / x); } for (int e: es) if (e != d) { int j = lower_bound(ds.begin(), ds.end(), e) - ds.begin(); a[i] -= a[j]; } } vector<i_i> ans(M); for (int i = 0; i < M; i++) ans[i]= i_i(ds[i], a[i]); return ans; } int main() { int H, W, K; cin >> H >> W >> K; vector<i_i> a = f(H), b = f(W); int sum = 0; for (i_i p: a) for (i_i q: b) sum = (sum + (ll)p.second * q.second % MOD * pow_mod(K, (ll)H * W / lcm(p.first, q.first), MOD)) % MOD; sum = (ll)sum * inv_mod((ll)H * W % MOD, MOD) % MOD; cout << sum << endl; }