#1186935 (C++23) No.377 背景パターン

• 問題: No.377 背景パターン
• ユーザー: vjudge1
• 提出日時: 2026-09-15 16:44:04
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,814 bytes
• コンパイル時間: 2,330 ms
• コンパイル使用メモリ: 347,112 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-15 16:44:10
• 合計ジャッジ時間: 4,847 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 5
other	AC * 2 WA * 12

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
#define endl "\n"
#define fi first
#define se second
using ll = long long;
using db = double;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ppii = pair<int, pii>;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;

template <const int m> 
struct Mint {
    int v; static_assert(m > 0);
    Mint(ll value = 0): v(value % m) { if (v < 0) v += m; }
    friend istream& operator >> (istream& inp, Mint& a) {
        ll x; inp >> x;
        a = x; return inp;
    }
    friend ostream& operator << (ostream& out, const Mint& a) { out << a.v; return out; }
    
    Mint operator + () const { return *this; }
    Mint operator - () const { return Mint() - *this; }
    
    Mint& operator++() { ++v; if (v == m) v = 1; return *this; }
    Mint& operator--() { if (v == 0) v = m; --v; return *this; }
    Mint operator++(int) { Mint ans = *this; ++*this; return ans; }
    Mint operator--(int) { Mint ans = *this; *this; return ans; }
    
    Mint& operator += (const Mint& other) { v += other.v; if (v >= m) v -= m; return *this; }
    Mint& operator -= (const Mint& other) { v -= other.v; if (v < 0) v += m; return *this; }
    Mint& operator *= (const Mint& other) { v = int64_t(v) * other.v % m; if (v < 0) v += m; return *this; }
    Mint inv() const {
        ll a = 1, b = 0;
        for (ll x = v, y = m; x != 0;)
            swap(a, b -= y / x * a), swap(x, y -= y / x * x);
        if (b < 0) b += m;
        return b;
    }
    Mint& operator /= (const Mint& other) { return *this *= other.inv(); }
    
    friend Mint operator + (const Mint& a, const Mint& b) { return Mint(a) += b; }
    friend Mint operator - (const Mint& a, const Mint& b) { return Mint(a) -= b; }
    friend Mint operator * (const Mint& a, const Mint& b) { return Mint(a) *= b; }
    friend Mint operator / (const Mint& a, const Mint& b) { return Mint(a) /= b; }
    
    friend bool operator == (const Mint& a, const Mint& b) { return a.v == b.v; }
    friend bool operator != (const Mint& a, const Mint& b) { return a.v == b.v; }
};

const int mod = 1e9 + 7;
using mint = Mint <mod>;

mint binpow(mint a, ll b){
    mint res = 1;
    while(b){
        if(b & 1) res *= a;
        a *= a;
        b /= 2;
    }
    return res;
}

mint inv(mint x){ return binpow(x, mod - 2); }

vector<int> U(int n){
    vector<int> v;
    for(int i = 1; i * i <= n; i++){
        if(n % i == 0){
            v.push_back(i);
            if(i * i != n) v.push_back(n / i);
        }
    }
    sort(v.begin(), v.end());
    return v;
}

ll lcm(ll x, ll y){
    return x / __gcd(x, y) * y;
}

const int N = 5e3 + 5;

ll sus[N];

void solve(){
    ll n, m, k;
    cin >> n >> m >> k;

    auto U1 = U(n), U2 = U(m);

    map<ll, mint> totient;
    sus[0] = 1;
    for(int i = 1; i < U1.size(); i++){
        for(int j = i - 1; j >= 0; j--){
            if(U1[i] % U1[j] != 0) continue;
            sus[i] = sus[j] * (U1[i] / U1[j] - 1);
            break;
        }
    }
    for(int i = 0; i < U1.size(); i++) totient[U1[i]] = sus[i];

    sus[0] = 1;
    for(int i = 1; i < U2.size(); i++){
        for(int j = i - 1; j >= 0; j--){
            if(U2[i] % U2[j] != 0) continue;
            sus[i] = sus[j] * (U2[i] / U2[j] - 1);
            break;
        }
    }
    for(int i = 0; i < U2.size(); i++) totient[U2[i]] = sus[i];

    mint res = 0;
    for(ll x : U1){
        for(ll y : U2){
            ll sus = n * m / lcm(n / __gcd(x, n), m / __gcd(y, m));
            res += binpow(k, sus) * totient[n / x] * totient[m / y];
        }
    }

    cout << res * inv(n * m);
}

int main(){
    if(fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
    solve();
}