#1168378 (C++14) No.3567 Modulo Grid

• 問題: No.3567 Modulo Grid
• ユーザー: hos.lyric
• 提出日時: 2026-06-05 23:25:06
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 39 ms / 2,000 ms
• コード長: 3,257 bytes
• コンパイル時間: 980 ms
• コンパイル使用メモリ: 149,812 KB
• 実行使用メモリ: 16,768 KB
• 最終ジャッジ日時: 2026-06-05 23:25:12
• 合計ジャッジ時間: 5,151 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

ファイルパターン	結果
sample	AC * 2
other	AC * 25

ソースコード

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T> ostream &operator<<(ostream &os, const vector<T> &as);
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


vector<vector<int>> solve(int M, int N) {
  if (M == 1 && N == 1) return {{0}};
  for (int p = 2; p <= M || p <= N; ++p) if (M % p == 0 || N % p == 0) {
    int m = M, n = N;
    int e = 0, f = 0;
    int q = 1;
    for (; m % p == 0; m /= p) { ++e; q *= p; }
    for (; n % p == 0; n /= p) { ++f; q *= p; }
    vector<pair<int, int>> gs(q);
    for (int r = 0; r < q; ++r) gs[r] = make_pair(__gcd(r, q), r);
    sort(gs.begin(), gs.end());
    vector<int> sg(q, -1);
    for (int h = 0; h < q; ++h) sg[gs[h].second] = h;
    const auto res = solve(m, n);
    vector<vector<int>> ret(M, vector<int>(N, -1));
    const int I = M/m, J = N/n;
    for (int x = 0; x < m; ++x) for (int y = 0; y < n; ++y) {
      for (int a = res[x][y]; a < M * N; a += m * n) {
        const int h = sg[a % q];
        const int i = h / J, j = h % J;
        ret[i * m + (i&1 ? (m-1-x) : x)][j * n + (j&1 ? (n-1-y) : y)] = a;
      }
    }
    return ret;
  }
  assert(false);
}

void stress() {
  constexpr int LIM = 10;
  for (int M = 1; M <= LIM; ++M) for (int N = 1; N <= LIM; ++N) {
    cerr << M << " " << N << endl;
    const auto ans = solve(M, N);
    for (int x = 0; x < M; ++x) cerr << ans[x] << endl;
    
    auto check = [&](int a, int b) -> void {
      a = __gcd(a, M * N);
      b = __gcd(b, M * N);
      assert(a % b == 0 || b % a == 0);
    };
    for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) {
      if (x + 1 < M) check(ans[x][y], ans[x + 1][y]);
      if (y + 1 < N) check(ans[x][y], ans[x][y + 1]);
    }
  }
}

int main() {
#ifdef LOCAL
  stress();
#endif
  
  int M, N;
  for (; ~scanf("%d%d", &M, &N); ) {
    auto ans = solve(M, N);
    for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) if (ans[x][y] == 0) ans[x][y] = M * N;
    
    for (int x = 0; x < M; ++x) {
      for (int y = 0; y < N; ++y) {
        if (y) printf(" ");
        printf("%d", ans[x][y]);
      }
      puts("");
    }
  }
  return 0;
}