TopCoder SRM 611 Div1 Easy LCMSet [1人競技プログラミング Advent Calendar 2016 11日目]

死ぬ程汚いコードを生み出してしまった…。

この記事は1人競技プログラミング Advent Calendar 2016 11日目の記事です。

問題概要：

TopCoder Statistics - Problem Statement

2以上1,000,000,000以下の整数がN(1<=N<=50)個入った整数の配列A、Bが与えられる。
配列Aの中の数字を任意に選択した際に作ることが出来る最小公倍数の集合と配列Bの中の数字を任意に選択した際に作ることが出来る最小公倍数の集合が一致しているかを判定せよ。

解いた方法：
全ての組み合わせを生成すると物凄いオーダーになり死ぬので別の方法を考える。
Bの配列にある全ての数をAの配列にある数の最小公倍数で作ることができ、Aの配列にある全ての数をBの配列にある数の最小公倍数で作ることが出来れば
お互いに作ることが出来る最小公倍数は一致する。

各数の素因数をmapで持っておき、ゴニョゴニョすればいけます…。(日本語にうまくまとめることが出来なかった。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class LCMSet {
    public:
    vector<int> A;
    vector<int> B;
    string equal(vector<int> _AA, vector<int> _BB) {
        A = _AA, B = _BB;

        vector<map<int,int>> A_map,B_map;

        REP(i, A.size()){
            int a = A[i];
            map<int, int> map_tmp;
            for(int j=2; j*j<= A[i]; j++){
                while(a % j == 0){
                    a /= j;
                    if(map_tmp.count(j) == 0) map_tmp.insert(MP(j,1));
                    else map_tmp[j] += 1;
                }
            }
            if(a != 1) map_tmp[a] = 1;
            A_map.PB(map_tmp);
        }

        REP(i, B.size()){
            int b = B[i];
            map<int, int> map_tmp;
            for(int j=2; j*j<= B[i]; j++){
                while(b % j == 0){
                    b /= j;
                    if(map_tmp.count(j) == 0) map_tmp.insert(MP(j,1));
                    else map_tmp[j] += 1;
                }
            }
            if(b != 1) map_tmp[b] = 1;
            B_map.PB(map_tmp);
        }

        REP(i, A.size()){
            map<int, int> now;
            REP(j, B.size()){
                bool flag = true;
                for(auto b : B_map[j]){
                    if(A_map[i].count(b.first) == 0 || A_map[i][b.first] < b.second){
                        flag = false;
                        break;
                    }
                }

                if(!flag) continue;

                for(auto b : B_map[j]){
                    if(A_map[i].count(b.first) == 1 && A_map[i][b.first] >= b.second){
                        if(now.count(b.first) == 0) now.insert(MP(b.first, b.second));
                        else now[b.first] = max(now[b.first], b.second);
                    }
                }
            }

            if(now != A_map[i]) return "Not equal";
        }

        REP(i, B.size()){
            map<int, int> now;
            REP(j, A.size()){
                bool flag = true;
                for(auto a : A_map[j]){
                    if(B_map[i].count(a.first) == 0 || B_map[i][a.first] < a.second){
                        flag = false;
                        break;
                    }
                }

                if(!flag) continue;

                for(auto a : A_map[j]){
                    if(B_map[i].count(a.first) == 1 && B_map[i][a.first] >= a.second){
                        if(now.count(a.first) == 0) now.insert(MP(a.first, a.second));
                        else now[a.first] = max(now[a.first], a.second);
                    }
                }
            }

            if(now != B_map[i]) return "Not equal";
        }

        return "Equal";
    }
};