14617 제 3회 IUPC

문제 추천을 받았는데 보자마자 무서운 문제란걸 바로 알았다.

Ai*Bi^x 0<=x<=Ci

이게 N개 주어진다. 여기서 같은건 묶는다고 하니 결국 unique한 요소의 수를 카운트 하는건데 난 이걸 지수함수로 보고 풀었다.

임의의 수 K가 있으면 K는 K를 구성하는 소수들의 곱으로 표현이 가능하다.

K = k1^f1(x) * k2^f2(x) * k3^f3(x) .....

i번째 지수함수와 j번째 지수함수가 같은 값을 가지기 위해서는

Ai*Bi^x = Aj*Bj^y

0<=x<=Ci

0<=y<=Cj

를 만족해야 하는데

이를 소수로 분해하면

(Ai를 구성하는 소수들의 곱) * (Bi를 구성하는 소수들의 곱)^x = (Aj를 구성하는 소수들의 곱) * (Bj를 구성하는 소수들의 곱)^y

로 표현된다.

소수끼리는 서로가 서로소이므로

왼쪽 항을 구성하는 소수들이

오른쪽 항을 구성하는 소수들과 구성이 맞아야 한다.

무슨 말이냐 하면 2*3^x랑 5*7^y는 x,y가 0보다 큰 정수인 한 죽어도 못만난다.

단 하나 예외는 y절편에서 만나는 것. 즉 x==0 || y==0인 경우 구성성분이 달라도 만날 수도 있다.

2*3^x = 2*5^y 에서 0,0을 해로 가지는 것 처럼.

A와 B는 둘 다 10만 이하 2 이상의 정수이므로 A*B에서 나올 수 있는 서로다른 소수의 개수는 많아봤자 9개밖에 안나온다.

(2 * 3 * 5 * 7 * 11 * 13 = 30030. 60060은 2^2 * 3 * 5 * 7 * 11 * 13 으로 표현되므로 소수의 종류는 그대로다.)

그렇게 되면 저기서 x,y에 관한 일차식을 최대 9개를 얻을 수 있는데 여기서 모두 연립하여 해를 구하면 된다.

ex )

2

30 900 5

60 450 5

A0 = 2 * 3 * 5

B0 = 2^2 * 3^2 * 5^2

A1 = 2^2 * 3 * 5

B1 = 2 * 3^2 * 5^2

왼쪽    : 2^(2x+1) * 3^(2x+1) * 5^(2x+1)

오른쪽 : 2^(y+2) * 3^(2y+1) * 5^(2y + 1)

이렇게 된다. 여기서 식을 뽑아내면

2x + 1 = y + 2

2x + 1 = 2y + 1

2x + 1 = 2y + 1

세가지가 나오는데 저걸 연립하면 결국 해가 없거나, 하나만 있거나, 범위거나가 된다.

--------------------------------------------------------------------------

코드 동작 방식

1. init()

 - 10만 이하의 소수를 모두 구해서 저장해놓는다(에라토스테네스의 체).

 - 겸사겸사 소수 i가 vector<int> 몇번에 저장되어 있는지 역추적하는 idx테이블도 만든다.

 - 10만 이하의 수를 가지고 빠르게 구성 성분을 구하기 위해서 dp테이블을 만든다.

(알고리즘 dp와는 무관하다. ex) dp[100000] = 2. 저걸 타고가면 10만을 구성하는 소수를 모두 알 수 있게 된다)

2. input()

 - 입력받아서 map에서 체크한다. Ai와 Bi가 이미 있다면 Ci만 비교해서 더 큰걸로 바꿔준다. 완전히 포함하는 함수기 때문에 작은건 무시한다.

 - 소수들로 분해해서 식을 저장해준다.

3. 0<=i<map.size(), i+1<=j<map.size()를 돌면서 i와 j가 동시에 가진 부분들을 체크 해제해 준다. 결국 i번째 지수함수가 유일하게 가지고 있는 부분만이 남기 때문에 겹치는 부분은 나중에 다 더해진다.

------------------------------------------------------------------------

처음에는 모두 식으로 처리하려고 했는데 i번째 식에서 j(i<j<n)번째 식을 뺄 때 중복되는걸 계속 빼는 문제가 있었다.

그래서 겹치는 부분을 모두 식으로 저장하고 점도 모두 저장하고 다음 식을 비교할 때 본래의 식이 아닌 저렇게 나뉜 식으로 비교하려고

해봤지만 지쳐서 그냥 x(0<=x<=100000) 배열만들어서 체크했다.

처음에 설계를 대충하고 그때그때 필요한걸 막 넣다보니 코드가 심각하게 더럽고 길다.

<코드>

#include <stdio.h>
#include <vector>
#include <cstring>
#include <algorithm>
#include <assert.h>
#include <map>
using namespace std;
#define arr_mv 100001
#define max_fac 9600
#define no_sol 0
#define one_sol 1
#define mul_sol 2
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
 
map<pii, pii> mset;
vector<ll> ps;
 
struct segm {
    int idx, bias, grad;
};
 
struct segments {
    int b, g, c;
    vector<segm> seg;
    segments() {
        b = g = c = 0;
    }
};
 
struct result_mat {
    int x, y, a, b, c;
    result_mat(int x = 0, int y = 0, int a = 0, int b = 0, int c = 0) :x(x), y(y), a(a), b(b), c(c) {}
};
 
inline ll gcd(ll a, ll b) { return a % b ? gcd(b, a%b) : b; }
 
int n, p[arr_mv], idx[arr_mv], cnt;
ll dp[arr_mv];
segments seg[101];
 
void init() {
    ps.push_back(2);
    for (ll i = 3; i < arr_mv; i += 2) {
        if (p[i]) continue;
        p[i] = 2;
        ps.push_back(i);
        idx[i] = ps.size() - 1;
        for (ll j = i * i; j < arr_mv; j += 2 * i)
            p[j] = 1;
    }
    for (int i = 1; i < arr_mv; i++) {
        for (auto j : ps) {
            if (i*j >= arr_mv) break;
            if (dp[i*j]) continue;
            dp[i*j] = j;
        }
    }
}
 
int classifier(result_mat a) {
    if (a.x == -1 && a.y == -1)
        return no_sol;
    else if (a.a == 1e7)
        return one_sol;
    else if (a.x == -1e7)
        return mul_sol;
}
 
result_mat calc_mat(result_mat fir, result_mat sec) {
    int fcls = classifier(fir);
    int scls = classifier(sec);
    if (fcls == no_sol || scls == no_sol) return result_mat(-1, -1, 0, 0, 0);
    if (fcls == one_sol) {
        if (scls == one_sol) {
            if (fir.x != sec.x || fir.y != sec.y) return result_mat(-1, -1, 0, 0, 0);
            else return fir;
        }
        else {
            if (sec.a*fir.x + sec.b*fir.y == sec.c) return fir;
            else return result_mat(-1, -1, 0, 0, 0);
        }
    }
    else {
        if (scls == one_sol) {
            if (fir.a*sec.x + fir.b*sec.y == fir.c) return sec;
            else return result_mat(-1, -1, 0, 0, 0);
        }
        else {
            int a = fir.a, b = fir.b, c = sec.a, d = sec.b;
            int e = fir.c, f = sec.c;
            int t = a * d - b * c;
            if (t == 0) {
                // 해가 무한할경우 : 식 두개가 같을 때 
                if (a*d & b*c) {
                    if (a*f == c*e)
                        return result_mat(-1e7, -1e7, a, b, e);
                    else
                        return result_mat(-1, -1, 0, 0, 0);
                }
                else if (!a && !b && !e)
                    return sec;
                else if (!c && !d && !f)
                    return fir;
                else if (!a && !c) {
                    if ((b && (e / b)*b != e) || (d && (f / d)*d != f)) 
                        return result_mat(-1, -1, 0, 0, 0);
                    else if (b && d && e / b == f / d) 
                        return fir;
                    else if (!b && !d) {
                        if (e == f) return fir;
                        else return result_mat(-1, -1, 0, 0, 0);
                    }
                    else
                        return result_mat(-1, -1, 0, 0, 0);
                }
                else if (!b && !d) {
                    if ((a && (e / a)*a != e) || (c && (f / c)*c != f)) 
                        return result_mat(-1, -1, 0, 0, 0);
                    else if (a && c && e / a == f / c) 
                        return fir;
                    else
                        return result_mat(-1, -1, 0, 0, 0);
                }
                else
                    return result_mat(-1, -1, 0, 0, 0);
            }
            else {
                int x = d * e + -b * f;
                int y = -c * e + a * f;
                if (t*x < 0 || t * y < 0)
                    return result_mat(-1, -1, 0, 0, 0);
                if (t < 0)
                    t = -t, x = -x, y = -y;
                if (x%t || y % t)
                    return result_mat(-1, -1, 0, 0, 0);
                return result_mat(x / t, y / t, 1e7, 1e7, 1e7);
            }
        }
    }
}
 
pipii counter(result_mat inp, int b1, int b2) {
    // binary search
    int l, r, minx, maxx, div;
    minx = b1 + 1;
    maxx = 0;
    // x가 증가하면 y도 증가
    if (inp.a*inp.b < 0) {
        l = 1; r = b1;
        // 최소
        while (l <= r) {
            int mid = (l + r) / 2;
            if (inp.b && (inp.c - inp.a*mid) / inp.b > 0) {
                minx = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        while (abs(inp.c - inp.a*minx) % abs(inp.b) && minx <= b1)
            minx++;
        // 최대
        l = 1; r = b1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (inp.b && (inp.c - inp.a*mid) / inp.b <= b2) {
                maxx = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        while (abs(inp.c - inp.a*maxx) % abs(inp.b) && maxx > minx)
            maxx--;
    }
    div = gcd(abs(inp.a), abs(inp.b));
    return pipii((abs(inp.b) / div), pii(minx, min(maxx, b1)));
}
 
void Input(int bias[max_fac], int grad[max_fac]) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a < 2 || a>100000 || b < 2 || b>100000 || c < 1 || c>100000) assert(0);
    pii &ex = mset[{a, b}];
    if (ex.first) {
        ex.first = max(ex.first, c);
        seg[ex.second].c = max(seg[ex.second].c, c);
        return;
    }
    
    ex = { c,cnt };
    seg[cnt].b = a; seg[cnt].g = b; seg[cnt].c = c;
 
    while (dp[a]) 
        bias[idx[dp[a]]]++, a /= dp[a];
    while (dp[b]) 
        grad[idx[dp[b]]]++, b /= dp[b];
 
    for (int j = 0; j < max_fac; j++) 
        if (bias[j] || grad[j]) 
            seg[cnt].seg.push_back({ j,bias[j],grad[j] });
    cnt++;
}
 
result_mat solve(int a, int b, int sz) {
    result_mat *arr = new result_mat[sz + sz % 2];
    int a_cnt = 0;
    for (int i = 0; i < sz; i++) {
        if (seg[a].seg[i].idx != seg[b].seg[i].idx)
            return result_mat(-1, -1, 0, 0, 0);
 
        arr[a_cnt] = result_mat(-1e7, -1e7, seg[a].seg[i].grad, -seg[b].seg[i].grad, seg[b].seg[i].bias - seg[a].seg[i].bias);
        if (!arr[a_cnt].a && !arr[a_cnt].b && !arr[a_cnt].c) a_cnt--;
        a_cnt++;
    }
    if (a_cnt % 2)
        arr[a_cnt] = arr[a_cnt - 1], a_cnt++;
 
    while (a_cnt > 1) {
        a_cnt = a_cnt / 2 + a_cnt % 2;
        for (int i = 0; i < a_cnt; i++)
            arr[i] = calc_mat(arr[2 * i], arr[2 * i + 1]);
        if (a_cnt % 2 && a_cnt != 1)
            arr[a_cnt] = arr[a_cnt - 1];
    }
    result_mat res = arr[0];
    delete[] arr;
    return res;
}
 
int cnter;
 
void push(pipii res, bool v[arr_mv]) {
    for (int k = res.second.first; k <= res.second.second; k += res.first) {
        cnter += v[k] ? 1 : 0;
        v[k] = 0;
    }
} 
 
int main() {
    init();
    scanf("%d", &n);
    ll ans = 0;
    int bias[max_fac], grad[max_fac];
    for (int i = 0; i < n; i++) {
        memset(bias, 0, sizeof(bias));
        memset(grad, 0, sizeof(grad));
        Input(bias, grad);
    }
    bool v[arr_mv];
    for (int i = 0; i < cnt; i++) {
        int sz = seg[i].seg.size();
        memset(v, true, sizeof(v));
        cnter = 0;
        for (int j = i + 1; j < cnt; j++) {
            ll Ai, Bi, Aj, Bj;
            Ai = seg[i].b; Bi = seg[i].g;
            Aj = seg[j].b; Bj = seg[j].g;
            // Ai * Bi^x == Aj
            int c = 0;
            while (Ai < Aj && Ai != Aj) Ai *= Bi, c++;
            if (c <= seg[i].c && Ai == Aj && v[c])
                v[c] = 0, cnter++;
 
            Ai = seg[i].b; Bi = seg[i].g;
            Aj = seg[j].b; Bj = seg[j].g;
            // Ai == Aj * Bj^x
            c = 0;
            while (Aj < Ai && Ai != Aj) Aj *= Bj, c++;
            if (c <= seg[j].c && Ai == Aj && v[0])
                v[0] = 0, cnter++;
 
            if (sz != seg[j].seg.size()) 
                continue;
 
            result_mat mat = solve(i, j, sz);
            int res_clas = classifier(mat);
            if (res_clas == mul_sol) {
                pipii res = counter(mat, seg[i].c, seg[j].c);
                if (res.second.first <= seg[i].c && res.second.second <= seg[i].c && res.second.first <= res.second.second)
                    push(res, v);
            }
            else if (res_clas == one_sol) {
                if (mat.x > seg[i].c || mat.y > seg[j].c) continue;
                vector<segm> pre = seg[i].seg;
                bool f = 1;
                for (int k = 0; k < pre.size(); k++) 
                    if (pre[k].grad*mat.x + pre[k].bias != seg[j].seg[k].grad*mat.y + seg[j].seg[k].bias) f = 0;
                if (f) {
                    cnter += v[mat.x] ? 1 : 0;
                    v[mat.x] = 0;
                }
            }
        }
        ans += seg[i].c + 1 - cnter;
    }
    printf("%lld\n", ans);
    return 0;
}