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

• 問題: No.377 背景パターン
• ユーザー: reginox
• 提出日時: 2026-09-24 00:04:05
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 254 ms / 5,000 ms
• コード長: 3,743 bytes
• コンパイル時間: 2,717 ms
• コンパイル使用メモリ: 366,160 KB
• 実行使用メモリ: 9,908 KB
• 最終ジャッジ日時: 2026-09-24 00:04:15
• 合計ジャッジ時間: 5,399 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef long double ld;

#define all(v) begin((v)), end((v))
#define Unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end());
#define lb(v, x) lower_bound((v).begin(), (v).end(), x) - (v).begin()
#define bit(x, y) (((x)>>(y))&1)
#define debug(x) cerr << (#x) << " " << (x) << endl
#define Timer 1.0 * clock() / CLOCKS_PER_SEC
ll rd(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}
const int mod = 1e9+7;
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 = 0; 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; }
};
using mint = Mint<mod>;

mint bpow(mint a, ll b){
  mint r = 1;
  while(b){
    if(b & 1) r *= a;
    a *= a;
    b >>= 1;
  }
  return r;
}

int h, w, k;
vector<pi> init(int x){
  vector<int> pf;
  for(int i = 1; i * i <= x; i++){
    if(x % i == 0){
      pf.push_back(i);
      if(i * i != x) pf.push_back(x / i);
    }
  }
  sort(all(pf));
  vector<pi> z(pf.size());
  for(int i = 0; i < pf.size(); i++){
    z[i].first = pf[i];
    int g = x/pf[i];
    int phi = g, v = g;
    for(int j = 2; j * j <= g; j++){
      if(v % j == 0){
        phi -= phi / j;
        while(v % j == 0) v /= j;
      }
    }
    if(v > 1) phi -= phi / v;
    z[i].second = phi;  
  }
  return z;
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> h >> w >> k;
  vector<pi> hp = init(h), wp = init(w); 
  // for(auto [x, y]:hp) cout << x << " " << y << "\n";
  // cout << "\n";
  // for(auto [x, y]:wp) cout << x << " " << y << "\n";

  mint ans = 0;
  for(auto &[x, y]:hp){
    for(auto &[u, v]:wp){
      ll val = (1ll * x * u) % (mod - 1);
      val = (1ll * val * gcd(h/x, w/u)) % (mod-1);
      // cout << x << " " << y << " " << u << " " << v << " " << val << "\n";
      ans += bpow(k, val) * y * v;
    }
  }
  // cout << ans << "\n";
  cout << ans * mint(1ll * h * w).inv();
  return 0;
}