結果

問題 No.377 背景パターン
ユーザー OIer1048576OIer1048576
提出日時 2024-06-22 18:39:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,191 bytes
コンパイル時間 1,723 ms
コンパイル使用メモリ 178,192 KB
実行使用メモリ 10,012 KB
最終ジャッジ日時 2024-06-22 18:40:02
合計ジャッジ時間 14,332 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) * __gcd(x, y));
        }
    }
    cout << (ans / Z(h) / Z(w)) << endl;
}
0