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

• 問題: No.377 背景パターン
• ユーザー: vjudge1
• 提出日時: 2026-09-15 17:38:15
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 399 ms / 5,000 ms
• コード長: 3,389 bytes
• コンパイル時間: 2,293 ms
• コンパイル使用メモリ: 346,460 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-15 17:38:25
• 合計ジャッジ時間: 4,478 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

ファイルパターン	結果
sample	AC * 5
other	AC * 14

ソースコード

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn=1e6+5, inf=1e18, mod=1e9+7;

struct DSU{
    int n;
    vector<int> p,sz;
    DSU(){};
    DSU(int n): n(n), p(n+1, 0), sz(n+1, 1){
        for(int i=1;i<=n;i++) p[i] = i;
    }
    int find_set(int u){
        return (u == p[u] ? u : p[u] = find_set(p[u]));
    }
    void union_set(int u, int v){
        u = find_set(u);
        v = find_set(v);
        if(u == v) return;
        if(sz[u] < sz[v]) swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
    }
};

ll h, w, k;


ll powmod(ll base, ll e){
    base %= mod;
    ll res = 1;
    while(e){
        if(e & 1) res = res * base % mod;
        base = base * base % mod;
        e >>= 1;
    }
    return res;
}

ll lcm(ll a, ll b){
    return (__int128_t)a * b / __gcd(a, b);
}

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

map<ll, ll> mp;

void precalc(vector<int> S1){
    for(int i = 0; i < S1.size(); i++){
        int v = S1[i] - 1;
        for(int j = i - 1; j >= 0; j--){
            if(S1[i] % S1[j] == 0 && S1[j] != 1){
                int d = __gcd(S1[j], S1[i] / S1[j]);
                v = (__int128_t)mp[S1[j]] * mp[S1[i] / S1[j]] * d / mp[d];
                break;
            }
        }
        mp[S1[i]] = (S1[i] == 1 ? 1 : v);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp", "r", stdin);
        freopen(__file_name ".out", "w", stdout);
    }
    // code here
    cin >> h >> w >> k;
//    for(int dh = 0; dh < h; dh++){
//        for(int dw = 0; dw < w; dw++){
//            DSU dsu(h * w);
//            for(int i = 0; i < h; i++){
//                for(int j = 0; j < w; j++){
//                    int i2 = (i + dh) % h, j2 = (j + dw) % w;
//                    dsu.union_set(i * w + j, i2 * w + j2);
//                }
//            }
//            cout << "(" << dh << "," << dw << ")\n";
//            set<int> S;
//            for(int i = 0; i < h; i++){
//                for(int j = 0; j < w; j++){
//                    S.insert(dsu.find_set(i * w + j));
//                    cout << dsu.find_set(i * w + j) << ' ';
//                }
//                cout << '\n';
//            }
//            // __gcd(__gcd(h, w), (ll)__gcd(dh, dw))
//            cout << S.size() << " - " << h / __gcd((ll)dh, h) << ' ';
//            cout << w / __gcd((ll)dw, w) << ' ' << (h * w) / lcm(h / __gcd((ll)dh, h), w / __gcd((ll)dw, w)) << '\n';
//            cout << "---\n";
//        }
//    }
    ll ans = 0;
    vector<int> S1 = facts(h), S2 = facts(w);
    precalc(S1); precalc(S2);
//    for(auto i: mp) cout << i.first << ' ' << i.second << '\n';
    for(int i: S1){
        for(int j: S2){
            ll p = h * w / lcm(h / i, w / j);
//            cout << "? " << mp[h / i] % mod << ' ' << mp[w / j] << '\n';
            ans = (ans + powmod(k, p) * mp[h / i] % mod * mp[w / j]) % mod;
            // __gcd((ll)i, h), __gcd((ll)j, w)
        }
    }
    cout << ans * powmod(h * w, mod - 2) % mod;
    return 0;
}