LG-P9031 [COCI2022-2023#1] Iksevi 题解
Tsawke
2023-03-28 15:08:26
# [LG-P9031 [COCI2022-2023#1] Iksevi](https://www.luogu.com.cn/problem/P9031) Solution
[TOC]
## [更好的阅读体验戳此进入](http://blog.tsawke.com?t=LG-P9031-Solution)
### 题面
$ n $ 次询问每次给定 $ x, y $ 求有多少个不同的正整数 $ d $ 满足 $ x = 2k_1d, y = (2k_2 + 1)d $ 或 $ x = (2k_1 + 1)d, y = 2k_2d $，其中 $ k_1, k_2 \in \mathbb{N} $。
### Solution
首先第一步就是将冗长的题面转换为上述式子，这是平凡且自然的。
考虑变形，以前者为例，不难想到有 $ 2k_1 = \dfrac{x}{d} $ 与 $ 2k_2 + 1 = \dfrac{y}{d} $，从代数意义上考虑，容易想到 $ \dfrac{x}{d} $ 为偶数，$ \dfrac{y}{d} $ 为奇数。这里我们考虑一些数论的常见套路，想到一个数质因数分解后有至少一个 $ 2 $ 当且仅当其为偶数（因为偶质数有且仅有 $ 2 $），则如果对 $ x, y $ 均质因数分解，那么 $ d $ 应满足其 $ 2 $ 的幂次严格小于 $ x $ 的 $ 2 $ 的幂次且洽等于 $ y $ 的 $ 2 $ 的幂次，而对于其它的奇质因子不难发现其幂次是任意的。
想到线性筛质数，然后通过质数之间的枚举幂次线性筛值域内所有数，求出其质因数分解后 $ 2 $ 的幂次与奇质因子幂次 $ +1 $ 后的乘积（对应上述的任意取幂次的方案数）。
此时考虑对于询问的每一对 $ x, y $，若 $ x = 0 \land y = 0 $，答案为 $ 0 $，若其中任意一个为 $ 0 $，答案显然为非零数质因数分解后奇质因子任取的方案数。若两者均为奇数，或两者质因数分解后 $ 2 $ 的幂次相同，那么 $ d $ 显然无法满足上述的 “严格小于 $ x $ 的 $ 2 $ 的幂次且洽等于 $ y $ 的 $ 2 $ 的幂次”，答案为 $ 0 $。否则我们直接取 $ \gcd(x, y) $ 质因数分解后奇质因子任取的方案数，这里也是自然的，即将 $ 2 $ 幂次较小数中 $ 2 $ 的幂次全部钦定取出使其最终为奇数，另一个即为偶数。
若值域为 $ v $，则预处理复杂度 $ O(v) $，单次询问复杂度 $ O(1) $，最终复杂度 $ O(v + n) $，限制最大值域后直接最优解（主要没几个人交）。
Tips：注意线性筛的过程中若后面的质数均无法取需直接回溯，否则会因大量枚举无用质数导致复杂度退化。
### Code
```cpp
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define P(i) (Prime.at(i - 1))
#define LIMV_SIZE (int)(1e7)
template < typename T = int >
inline T read(void);
int N;
int tot;
int LIMV(0);
pair < int, int > pos[1100000];
bitset < LIMV_SIZE + 114514 > notPrime;
basic_string < int > Prime;
pair < int, int > fact[LIMV_SIZE + 114514];
int main(){
N = read();
for(int i = 1; i <= N; ++i)LIMV = max({LIMV, pos[i].first = read(), pos[i].second = read()});
for(int i = 2; i <= LIMV; ++i){
if(!notPrime[i])Prime += i;
for(auto p : Prime){
if((ll)i * p > LIMV)break;
notPrime[i * p] = true;
if(i % p == 0)break;
}
}tot = Prime.size();
auto dfs = [](auto&& self, int dep = 1, int cnt2 = 0, int cnt_odd = 1, ll val = 1)->void{
if(val > LIMV)return;
if(dep > tot || val * P(dep) > LIMV)return fact[val] = {cnt2, cnt_odd}, void();
int tims(1);
while(val <= LIMV){
self(self, dep + 1, cnt2, cnt_odd, val);
val *= P(dep);
if(P(dep) == 2)++cnt2;
else cnt_odd /= tims, cnt_odd *= ++tims;
}
}; dfs(dfs);
for(int i = 1; i <= N; ++i){
int X = pos[i].first, Y = pos[i].second;
if(!X && !Y){printf("0\n"); continue;}
if(!X || !Y){printf("%d\n", fact[X ^ Y].second); continue;}
int pow2X = fact[X].first, pow2Y = fact[Y].first;
if((!pow2X && !pow2Y) || pow2X == pow2Y){printf("0\n"); continue;}
printf("%d\n", fact[__gcd(X, Y)].second);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}ret *= flag;
return ret;
}
```
## UPD
update-2023_03_28 初稿