#1169780 (C++23) No.3567 Modulo Grid

• 問題: No.3567 Modulo Grid
• ユーザー: pockyny
• 提出日時: 2026-06-28 18:46:10
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 65 ms / 2,000 ms
• コード長: 2,384 bytes
• コンパイル時間: 1,397 ms
• コンパイル使用メモリ: 172,864 KB
• 実行使用メモリ: 36,980 KB
• 最終ジャッジ日時: 2026-06-28 18:46:19
• 合計ジャッジ時間: 6,110 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

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

ソースコード

#include <iostream>
#include <vector>

using namespace std;
typedef vector<vector<int>> mat;

// (m,n),(p,q) -> (m*p,n*q) で反転あり
mat matrix_tensor_product(mat a,mat b){
    int m = a.size();
    int n = a[0].size();
    int p = b.size();
    int q = b[0].size();
    mat ret(m*p,vector<int>(n*q));
    int i,j,l,r;
    for(i=0;i<p;i++){
        for(j=0;j<q;j++){
            for(l=0;l<m;l++){
                for(r=0;r<n;r++){
                    ret[i*m + l][j*n + r] = a[l][r]*b[i][j];
                }
            }
        }
    }
    for(i=1;i<p;i+=2){
        for(j=0;j<n*q;j++){
            // 上下反転
            for(l=0;l<m/2;l++){
                swap(ret[i*m + l][j],ret[(i + 1)*m - 1 - l][j]);
            }
        }
    }
    for(j=1;j<q;j+=2){
        for(i=0;i<m*p;i++){
            // 左右反転
            for(l=0;l<n/2;l++){
                swap(ret[i][j*n + l],ret[i][(j + 1)*n - 1 - l]);
            }
        }
    }
    return ret;
}

int gcd(int a,int b){
    if(a<b) swap(a,b);
    if(b==0) return a;
    return gcd(a%b,b);
}

int pw(int a,int x){
    int ret = 1;
    while(x){
        if(x&1) ret *= a;
        (a *= a); x /= 2;
    }
    return ret;
}

// (p^x,p^y)で条件を満たすやつを作る
mat createMat(int x,int y,int p){
    int i,j,mx = pw(p,x + y);
    mat ret(pw(p,x),vector<int>(pw(p,y)));
    for(i=0;i<pw(p,x);i++){
        for(j=0;j<pw(p,y);j++){
            ret[i][j] = gcd(mx,i*pw(p,y) + j + 1);
        }
    }
    return ret;
}

const int MX = 200000;
vector<int> v[MX + 10];
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int i,j,h,w; cin >> h >> w;
    for(i=1;i<=h*w;i++){
        v[gcd(h*w,i)].push_back(i);
    }
    mat m(1,vector<int>(1,1));
    int H = h,W = w;
    for(i=2;i<=MX;i++){
        if(H%i==0 || W%i==0){
            int c = 0,d = 0;
            while(H%i==0){
                c++; H /= i;
            }
            while(W%i==0){
                d++; W /= i;
            }
            mat m2 = createMat(c,d,i);
            m = matrix_tensor_product(m,m2);
        }
    }
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            int x = m[i][j];
            m[i][j] = v[x].back();
            v[x].pop_back();
        }
    }
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            cout << m[i][j] << " ";
        }
        cout << "\n";
    }
}