题解 CF571E 【Geometric Progressions】
CYJian
·
·
题解
upd: 修正了亿些小问题
首先发现这个乘积会很大，直接存不方便，不如质因数分解后存指数。
然后再考虑怎么做：
我们考虑每次对两个集合取交集，显然只会有三种情况分类讨论：
- 交集为空集：显然确定了答案为 -1。
- 交集为一个数：那么只需考虑这个数是否存在在后面的集合中就行了。
- 交集为一个集合：这个集合显然可以用与其他集合相同的方法表示，相当于合并了两个集合。
那么如果没有出现前两种情况，只要能做完 n-1 次合并，我们就只需要输出最后的集合的 a 就行了。（a 的含义同题面）
考虑如何进行合并的过程：
设 c_p(x) 为 x 的质因数分解中 p 的个数。
我们考虑对于第 i 个集合的 a_i 和 b_i 进行质因数分解后，集合内的第 j 个数 s_{i,j} 满足对于任意质数 p，c_p(s_{i,j})=c_p(a_i)+(j - 1) \times c_p(b_i)。
考虑合并两个集合，那么可以考虑枚举质数 p。然后分以下三种情况讨论：
- 两个集合的 c_p(b_i) 都为 0：仅需判断两个集合的 c_p(a_i) 是否相等。若相等则考虑下一个质数 p；若不相等则一定不合法。
- 只有一个集合的 c_p(b_i) 为 0：那么对于这个质数 p 的指数是一定是固定了的。那么对于 c_p(b_i) 不为零的那一个集合就可以唯一确定 c_p(s_{i,j})=c_p(a_i)+(j - 1) \times c_p(b_i) 的 j，那么就相当于将可能属于并集的数的个数限制在了这一个数上，就可以判断这个数是不是所有集合的并就行了。
- 两个集合的 c_p(b_i) 都不为 0：先放着不管，之后讨论这个问题。
处理完所有质数之后，若还没结束合并，那么就是存在若干个质数都属于情况三。考虑情况三的本质是若干个如下的方程：
c_p(a_i) + x \times c_p(b_i) = c_p(a_j) + y \times c_p(b_j)
不难发现移项后就是关于 x,y 的二元一次方程（组）。考虑删除掉重复的方程后（将系数同时除掉最大公约数），若方程数大于等于 2，那么就一定能解出一组解，或者无解。这分别对应第一次分类讨论中的第二个、第一个情况。
如果只有一个方程，那么就需要解一个不定方程：用扩展欧几里得算法解出 x 和 y 的最小非负整数解或者判断无解。若存在非负整数解，则可以将集合的交集写成这样的形式：（设 x_0 为上面方程的 x 的最小非负整数解）
c_p(a')=c_p(a_i) + x_0 \times c_p(b_i)
c_p(b')=lcm(c_p(b_i), c_p(b_j))
然后接着与下一个方程合并就行了。
合并到最后，a' 作为答案就行了。
当然，如果为了方便，不把第一次分类讨论的第二种情况单独拿出来考虑，放入第三种情况以节约码量也行。（我就是这么写的）
```cpp
const int mod = 1e9 + 7;
inline int fsp(int x, ll k) {
int s = 1;
while(k) {
if(k & 1) s = 1LL * s * x % mod;
x = 1LL * x * x % mod, k >>= 1;
} return s;
}
inline ll exgcd(ll a, ll b, ll&x, ll&y) {
if(!b) return x = 1, y = 0, a;
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
struct Node {
ll k, b;
Node() {}
Node(int k, int b):k(k), b(b) {}
};
int a[110];
int b[110];
int P[6100];
Node f[6100];
Node g[6100];
int N;
inline void GetPri(int x) {
int t = x;
for(int i = 2; i * i <= x; i++) {
if(t % i == 0) {
P[++N] = i;
while(t % i == 0) t /= i;
}
} if(t > 1) P[++N] = t;
}
struct Func {
ll A, B, C;
Func() {}
Func(ll A, ll B, ll C):A(A), B(B), C(C) {}
};
int vis = 0;
inline int solve(int b, int k) {
for(int i = 1; i <= N; i++) g[i] = Node(0, 0);
for(int i = 1; i <= N; i++) {
while(k % P[i] == 0) k /= P[i], ++g[i].k;
while(b % P[i] == 0) b /= P[i], ++g[i].b;
}
if(!vis) {
for(int i = 1; i <= N; i++) f[i] = g[i];
vis = 1;
return 1;
}
for(int t = 0; t < 3; t++) {
for(int i = 1; i <= N; i++) {
ll fb = f[i].b;
ll fk = f[i].k;
ll gb = g[i].b;
ll gk = g[i].k;
if(!fk && !gk) {
if(fb != gb) return 0;
} else if(!fk || !gk) {
int tag = 0;
if(!fk) swap(fk, gk), swap(fb, gb), tag = 1;
if(gb < fb || (gb - fb) % fk) return 0;
ll k = (gb - fb) / fk;
if(tag)
for(int j = 1; j <= N; j++)
g[j].b += g[j].k * k, g[j].k = 0;
else
for(int j = 1; j <= N; j++)
f[j].b += f[j].k * k, f[j].k = 0;
}
}
}
Func F;
int flag = 0;
ll X = -1, Y = -1;
for(int i = 1; i <= N; i++) {
ll fb = f[i].b;
ll fk = f[i].k;
ll gb = g[i].b;
ll gk = g[i].k;
if(fk && gk) {
if(!flag) F = Func(fk, -gk, gb - fb), flag = 1;
else if(flag == 1) {
ll A = fk, B = -gk, C = gb - fb;
ll d = __gcd(F.A, A);
ll m1 = A / d;
ll m2 = F.A / d;
F.A *= m1, F.B *= m1, F.C *= m1;
A *= m2, B *= m2, C *= m2;
if(F.A == A && F.B == B) {
if(F.C != C) return 0;
else {
ll d = __gcd(__gcd(F.A, abs(F.B)), abs(F.C));
F.A /= d, F.B /= d, F.C /= d;
continue;
}
} else {
C -= F.C, B -= F.B;
if(C < 0) C *= -1, B *= -1;
if(B < 0 || C % B) return 0;
Y = C / B;
X = (F.C - F.B * Y) / F.A;
if(X < 0 || (F.C - F.B * Y) % F.A) return 0;
flag = 2;
}
} else if(flag == 2) {
ll A = fk, B = -gk, C = gb - fb;
if(A * X + B * Y != C) return 0;
}
}
}
if(flag == 2) {
for(int i = 1; i <= N; i++)
f[i].b += f[i].k * X, f[i].k = 0;
}
if(flag == 1) {
ll x, y;
ll d = exgcd(F.A, -F.B, x, y);
y = -y;
if(F.C % d) return 0;
ll kx = -F.B / d;
ll ky = F.A / d;
x *= F.C / d;
y *= F.C / d;
ll tx = 0, ty = 0;
if(x < 0) tx = -((-x + kx - 1) / kx);
else tx = x / kx;
if(y < 0) ty = -((-y + ky - 1) / ky);
else ty = y / ky;
x -= kx * min(tx, ty);
y -= ky * min(tx, ty);
for(int i = 1; i <= N; i++)
f[i].b += f[i].k * x, f[i].k *= kx;
}
return 1;
}
int main() {
int n = ri;
for(int i = 1; i <= n; i++) {
GetPri(a[i] = ri);
GetPri(b[i] = ri);
}
sort(P + 1, P + 1 + N);
N = unique(P + 1, P + 1 + N) - P - 1;
for(int i = 1; i <= n; i++)
if(!solve(a[i], b[i])) return puts("-1"), 0;
int res = 1;
for(int i = 1; i <= N; i++)
res = 1LL * res * fsp(P[i], f[i].b) % mod;
cout << res << endl;
return 0;
}
```