結果
| 問題 | No.377 背景パターン |
| ユーザー |
 OIer1048576
|
| 提出日時 | 2024-06-22 18:43:57 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 962 ms / 5,000 ms |
| コード長 | 4,249 bytes |
| コンパイル時間 | 1,686 ms |
| コンパイル使用メモリ | 178,428 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-22 18:44:05 |
| 合計ジャッジ時間 | 4,308 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 14 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <int MOD>struct modint {int val;static int norm(const int& x) { return x < 0 ? x + MOD : x; }static constexpr int get_mod() { return MOD; }modint inv() const { return pow(MOD - 2); }modint() : val(0) {}modint(const int& m) : val(norm(m)) {}modint(const long long& m) : val(norm(m % MOD)) {}modint operator-() const { return modint(norm(-val)); }bool operator==(const modint& o) { return val == o.val; }bool operator<(const modint& o) { return val < o.val; }modint& operator+=(const modint& o) {return val = (1ll * val + o.val) % MOD, *this;}modint& operator-=(const modint& o) {return val = norm(1ll * val - o.val), *this;}modint& operator*=(const modint& o) {return val = static_cast<int>(1ll * val * o.val % MOD), *this;}modint& operator/=(const modint& o) { return *this *= o.inv(); }modint& operator^=(const modint& o) { return val ^= o.val, *this; }modint& operator>>=(const modint& o) { return val >>= o.val, *this; }modint& operator<<=(const modint& o) { return val <<= o.val, *this; }modint operator-(const modint& o) const { return modint(*this) -= o; }modint operator+(const modint& o) const { return modint(*this) += o; }modint operator*(const modint& o) const { return modint(*this) *= o; }modint operator/(const modint& o) const { return modint(*this) /= o; }modint operator^(const modint& o) const { return modint(*this) ^= o; }modint operator>>(const modint& o) const { return modint(*this) >>= o; }modint operator<<(const modint& o) const { return modint(*this) <<= o; }friend std::istream& operator>>(std::istream& is, modint& a) {long long v;return is >> v, a.val = norm(v % MOD), is;}friend std::ostream& operator<<(std::ostream& os, const modint& a) {return os << a.val;}friend std::string tostring(const modint& a) {return std::to_string(a.val);}friend modint qpow(const modint& a, const long long& b) {assert(b >= 0);modint x = a, res = 1;for (int p = b; p; x *= x, p >>= 1)if (p & 1) res *= x;return res;}modint pow(const long long& b) const { return qpow(*this, b); }};using M107 = modint<1000000007>;using M998 = modint<998244353>;using Mint = M107;// constexpr mod = ...;// using Mint = modint<mod>;struct Fact {std::vector<Mint> fact, factinv;const int n;Fact(const int& _n) : n(_n), fact(_n + 1, Mint(1)), factinv(_n + 1) {for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;factinv[n] = fact[n].inv();for (int i = n; i; --i) factinv[i - 1] = factinv[i] * i;}Mint C(const int& n, const int& k) {if (n < 0 || k < 0 || n < k) return 0;return fact[n] * factinv[k] * factinv[n - k];}Mint A(const int& n, const int& k) {if (n < 0 || k < 0 || n < k) return 0;return fact[n] * factinv[n - k];}};using Z = M107;set<int> prime_scanned;vector<int> factor(int n) {vector<int> factors;for (int i = 1; i * i <= n; i++)if (n % i == 0) {factors.push_back(i);if (i * i != n) factors.push_back(n / i);}for (int i = 2; i * i <= n; i++)if (n % i == 0) {prime_scanned.insert(i);while (n % i == 0) {n /= i;}}if (n != 1) prime_scanned.insert(n);return factors;}int totient(int x) {int ans = x;for (int p : prime_scanned) {if (x % p == 0) {while (x % p == 0) x /= p;ans -= ans / p;}}return ans;}int main() {// B 题实在写不动了.. D 题反倒推出来了..int h, w, k;cin >> h >> w >> k;auto h_ = factor(h);auto w_ = factor(w);Z ans = 0;for (auto x : h_) {for (auto y : w_) {ans += Z(1) * totient(x) * totient(y) *Z(k).pow(1ll * (h / x) * (w / y) % (1000000006) *__gcd(x, y) % (1000000006));}}cout << (ans / Z(h) / Z(w)) << endl;}