20211115 数字 num
Description
假设一棵树的形态是一个点连向在线性筛中它筛到的点,其中 \(1\) 连向所有质数。
现在有 \(m\) 个询问,每次给定 \(x\) 和 \(y\) ,问两个点的 \(lca\) 。
\(m\leq 10 ^6 ;\ x ,\ y \leq 10 ^ 9\)
Analysis
由于线性筛的特性,所以每个点的父亲等于该点除以最小质因子。
所以 \(lca\) 就一定是两个数的质因数从大到小排序后的最长的相等的前缀。
画画图就能发现啦!
Solution
接着 Analysis 的想法,看得出来正解是要 \(m\log\) 级别的做法,但目前分解质因数的话还只是 \(\sqrt {num}\) 级别的,考虑怎么优化。
发现线性筛可以一路干到 \(10 ^ 7\) ,所以我们可以在线性筛的时候记录每个点的最小质因子。
然后众所周知一个数的质因子数量是不超过 \(\log\) 级别的,所以小于 \(10 ^ 7\) 的数可以 \(\log\) 做。
现在再考虑剩下的怎么做:
发现我们对于单个值的分解就那么快,加速不了,那么去利用两个值的共性。就比如 \(gcd\) 什么的。
我们发现 \(gcd\) 就是两个值所有相同的质因子,然后按照 Analysis ,可能 \(x\) 和 \(y\) 剩下的值有些质因子比 \(gcd\) 里面的一些质因子大,就挡住了去路,如果能处理掉就是答案了,所以就可以根据 \(\frac{x}{gcd},\space \frac{y}{gcd},\space gcd\) 的大小看是用谁去处理谁。
-
\(gcd \geq 10 ^ 7\) :用剩下的 \(x\) 和 \(y\) 直接去掉 \(gcd\) 不合法的质因子就可以了。
-
\(\frac{x}{gcd},\space \frac{y}{gcd},\space gcd \leq 10 ^ 7\) :用前面说的处理小于 \(10 ^ 7\) 的数的办法处理这三个数即可。
-
\(\frac{x}{gcd},\space \frac{y}{gcd} \geq 10 ^ 7\) :用 \(gcd\) 去找在哪个质因子之后能把剩下的 \(x\) 和 \(y\) 处理干净(就是只剩 \(1\) 了),哪个地方就是答案的开始。
那这样的话全部数都可以在 \(\log\) 的时间搞定,整个题目也就搞定了!
Code
/*
这是一个屑写的代码
*/
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, M = 1e7 + 10;
int n, x, y, z, pri[M], cnt, vis[M];
inline int read() {
char ch = getchar();
int s = 0, w = 1;
while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
return s * w;
}
inline int gcd(int a, int b) {
return (!b) ? a : gcd(b, a % b);
}
inline void prime() {
for (int i = 2; i <= 1e7; ++i) {
if (!vis[i]) pri[++cnt] = i, vis[i] = 1;
for (int j = 1; j <= cnt; ++j) {
if (i * pri[j] > 1e7) break;
vis[i * pri[j]] = i;
if (i % pri[j] == 0) break;
}
}
}
inline void mian() {
x = read(), y = read(); z = gcd(x, y);
if (z == 1) {
printf("1\n");
return ;
}
x /= z; y /= z;
if (z <= 1e7) {
if (max(x, y) <= 1e7) {
int mx = 0;
while (vis[x] > 1) x = vis[x];
while (vis[y] > 1) y = vis[y];
mx = max(x, y);
while (vis[z] > 0 && (z / vis[z] < mx)) z = vis[z];
printf("%d\n", z);
}
else {
int mx = 0;
for (int i = 1; i <= cnt && pri[i] <= z; ++i) {
if (x % pri[i] == 0) {
mx = pri[i];
while (x % pri[i] == 0) x /= pri[i];
}
if (y % pri[i] == 0) {
mx = pri[i];
while (y % pri[i] == 0) y /= pri[i];
}
}
if (x != 1 || y != 1) {
printf("1\n"); return ;
}
while (vis[z] > 0 && (z / vis[z] < mx)) z = vis[z];
printf("%d\n", z);
}
}
else {
int mx = 0;
for (int i = 1; i <= cnt && pri[i] <= max(x, y); ++i) {
if (x % pri[i] == 0 || y % pri[i] == 0) mx = i;
}
for (int i = 1; i < mx; ++i) {
if (z % pri[i] == 0) {
while (z % pri[i] == 0) z /= pri[i];
}
}
printf("%d\n", z);
}
}
int main() {
// freopen("num.in", "r", stdin);
// freopen("num.out", "w", stdout);
prime();
n = read();
while (n--) mian();
return 0;
}