题解 P1072 【Hankson 的趣味题】
皎月半洒花
2018-08-19 00:24:20
没错我不是来宣传正解的，我是来说一种毒瘤解法的 $233$。
哦哦，如果你不想看讲基本做法。你可以向下翻$233$。
嗯，其实遇到这种单纯的$gcd \ \ or \ \ lcm$的题，我们都可以用一种比较简单的方法分析：唯一分解定理。
嗯，是整数域的唯一分解，不是多项式域的唯一分解。
那么其实其他的大佬已经解释得很清楚了，关于这种解法，大部分来讲都是先筛出数据范围上限$\sqrt n$即可。但是有个$Bug$就是对于每个合数$k$，都最多有一个质因子是大于$\sqrt k$的由于数据范围过大窝萌没法直接筛，而我正是解决了这个问题（虽然有点慢$233$）.
我们思考对于$a_0$和$a_1$而言，假设$gcd(x,a_0)=a_1$
那么我们会有比较浅显的结论：若
$$
a_0=\prod\limits_{i=1}^{m}p_i^{c_i}~~,~~x=\prod\limits_{i=1}^{n}p_i^{d_i}
$$
那么
$$
a_1=\prod\limits_{i=1}^{max(m,n)}p_i^{min(c_i,d_i)}
$$
那我们反着考虑，对于他们的 $gcd$——$a_1$ 里的 $p_i$ 来讲，要么是$a_0$中的，要么是$x$中的。换句话说，如果$c_i = min(c_i,d_i)$，那么$d_i$只需要$\geq~c_i$即可，也就是说$d_i$可以在区间 $[c_i,\infty)$ 上随便取，我们现在称这个$x$为**自由未知数（$free\ \ uknown -number$）**，称这个区间为**自由区间（$free\ \ ranges$）**。
而如果不一样，就只可能是 $c_i>min(d_i,c_i)$，此时没有任何取法，只有可能是 $d_i=min(d_i,c_i)$，所以就只能有一种选法，我们现在称这个$x$为**非自由未知数（$unfree\ \ uknown-number$）**。
同理，$lcm$那部分也一样。
但是这个地方需要注意的是，我们需要考虑$2^2$种不同情况：
$1$、两个方程的$x$均非自由，那么如果不同的话就会无解。
$2 \&3$、$gcd$或者$lcm$中有一个非自由，我们需要判断这个非自由的解是否是在另一个的自由区间内，不在就是不合法。
$4$、都是自由的，那么就做个差留到最后乘法原理。
代码大概长这样：
```cpp
inline void Linearity(){
T = qr() ;
Chk[1] = Chk[0] = 1 ;
for (i = 2 ; i <= MAX ; ++ i){
if (!Chk[i]) P[++ P[0]] = i ;
for (j = 1; j <= P[0] && i * P[j] <= MAX ; ++ j){
Chk[i * P[j]] = 1 ;
if (i % P[j] == 0) break ;
}
}
}
inline void work(int ST, int ED){
for(i = ST; i <= ED ; ++ i){
N1 = N2 = N3 = N4 = 0 ;
while (!(A0 % P[i])) A0 /= P[i], ++ N1 ;
while (!(A1 % P[i])) A1 /= P[i], ++ N2 ;
while (!(B0 % P[i])) B0 /= P[i], ++ N3 ;
while (!(B1 % P[i])) B1 /= P[i], ++ N4 ;
if (N1 > N2 && N3 < N4){
if (N2 == N4) A[i] = B[i] = 1 ;
else {mark = 0; break ;}
continue ;
}
if (N1 > N2){
if (N4 >= N2) A[i] = B[i] = N2 ;
else {mark = 0; break ;}
continue ;
}
if (N3 < N4){
if (N4 >= N2) A[i] = B[i] = N3 ;
else {mark = 0; break ;}
continue ;
}
else {
if (N4 >= N2) A[i] = N2, B[i] = N4 ;
else {mark = 0; break ;}
}
}
}
```
那么接下来的问题就是该怎么确定最后一个质因子。有一个很显然的做法是由于是最后一个质因子，所以我们只需要判断一下分解完质因数每一个是不是$1$即可，不是$1$的话，那就肯定是未筛到的，我们直接让他加入$prime$数组即可。哦，对，还需要再筛一遍，详情看代码即可。
```cpp
#include <cstdio>
#include <bitset>
#include <iostream>
#define MAX 45000
#define ll long long
using namespace std ;
bitset <MAX> Chk ; int A0, A1, B0, B1 ;
int Ans, T, i, j, P[MAX >> 2] ; bool mark ;
int N1, N2, N3, N4, A[MAX >> 2], B[MAX >> 2], Txt ;
inline int qr(){
int k = 0 ; char c = getchar() ;
while(!isdigit(c)) c = getchar() ;
while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = getchar() ;
return k ;
}
inline void Linearity(){
T = qr() ;
Chk[1] = Chk[0] = 1 ;
for (i = 2 ; i <= MAX ; ++ i){
if (!Chk[i]) P[++ P[0]] = i ;
for (j = 1; j <= P[0] && i * P[j] <= MAX ; ++ j){
Chk[i * P[j]] = 1 ;
if (i % P[j] == 0) break ;
}
}
}
inline void work(int ST, int ED){
for(i = ST; i <= ED ; ++ i){
N1 = N2 = N3 = N4 = 0 ;
while (!(A0 % P[i])) A0 /= P[i], ++ N1 ;
while (!(A1 % P[i])) A1 /= P[i], ++ N2 ;
while (!(B0 % P[i])) B0 /= P[i], ++ N3 ;
while (!(B1 % P[i])) B1 /= P[i], ++ N4 ;
if (N1 > N2 && N3 < N4){
if (N2 == N4) A[i] = B[i] = 1 ;
else {mark = 0; break ;}
continue ;
}
if (N1 > N2){
if (N4 >= N2) A[i] = B[i] = N2 ;
else {mark = 0; break ;}
continue ;
}
if (N3 < N4){
if (N4 >= N2) A[i] = B[i] = N3 ;
else {mark = 0; break ;}
continue ;
}
else {
if (N4 >= N2) A[i] = N2, B[i] = N4 ;
else {mark = 0; break ;}
}
}
}
int main(){
freopen("son.in", "r", stdin) ;
freopen("son.out", "w", stdout) ;
Linearity() ;
while(T --){
Ans = 1, mark = 1 ;
A0 = qr(), A1 = qr(), B0 = qr(), B1 = qr() ;
work(1, P[0]) ;
if (A0 != 1 || A1 != 1 || B0 != 1 || B1 != 1){
Txt = P[0] + 1 ;
if (B1 != 1) P[++ P[0]] = B1 ;
if (A1 != 1 && A1 != B1) P[++ P[0]] = A1 ;
if (A0 != 1 && A0 != B1 && A0 != A1) P[++ P[0]] = A0 ;
if (B0 != 1 && B0 != B1 && B0 != A1 && B0 != A0) P[++ P[0]] = B0 ;
work(Txt, P[0]) ;
}
for(i = 1; i <= P[0] && mark ; ++ i) Ans *= (B[i] - A[i] + 1) ;
if (!mark) putchar('0'), putchar('\n') ;
else printf("%d\n", Ans) ;
}
}
```
最后还有彩蛋哦：
$1$、这个题中的关键代码，就是work函数是在作者事先考虑清楚，事中如同做梦，事后不可思议的情况下写出来的……也就是说当时写代码的时候码力突然增强了一个量级$2333$
$2$、关于什么自由不自由的定义……哈哈哈哈那只是我的突发奇想而已~~不是故意哲学!不是！~~但是你会发现以下的文字阐述确实会简练好多啊
$3$、其实你如果去不找另一个比较大的质数，也是可以得$90$分的！从$loj$的数据来看，前面的测试点一路顺风，只有最后一个测试点是专门卡这一点的，因为出现了好多行答案不相同的情况$2333$
$4$、其实我觉得我最后的操作是跟$AlphaGo$动态学习处理信息有点异曲同工之处的，所以为了这个必须来写题解！