生日礼物

我觉得还算简单的一道数学题吧

Luogu T2069 生日礼物

题面

$lcm(a, b) == n$ ,求$a, b$的对数

输入 n, 输出方案数

数据范围

n <= 10^16

思路

考虑两个数的lcm

分解质因数的话

$a = p_1^{qa_1} \times p_2^{qa_2} \times … \times p_m^{qa_m}$

$b = p_1^{qb_1} \times p_2^{qb_2} \times … \times p_m^{qb_m}$

假设 $c = lcm(a,b)$

$c = p_1^{qc_1} \times p_2^{qc_2} \times … \times p_m^{qc_m}$

那么有

$qc_i = max(qa_i, qb_i), i \in [1, m]$

那么就可以开始排列了

对于每一个可以分解出来的质数 $p_i$

$a,b$ 至少有一个的质数是 $qc_i$

也就是 $qa_i == qc_i || qb_i == qc_i$

假如两个都是 $qc_i$ 就只有一种情况

假如只有一个是 $qc_i$ ,那么另一个可以是 $[0, qc_i-1]$

因为 $p_i^0 = 1$ ,就相当于这个数分解不出这样一个质数

结果大概是对于 $lcm(a,b)分解质因数$

然后答案是 $\prod\limits_{i=1}^{m}qc_i*2+1$

引申到大范围来说,如果某个质数$p$并不在分解出的范围内

那么对结果的影响也就是乘上一个 1, 所以也是正确的


核心思路如上

本题还有一些要注意的地方

质因数分解理想复杂度是 $O(\sqrt{n})$

事实上并非如此

如果 n 一开始就是一个大素数,就T了

因此应对的策略其实也很简单

一开始特判一下

还有就是如果 n 是几个大素数的乘积

那也比较麻烦,所以每分解一个质数再判断一下

ps: 即使用非常朴素的判断方法也快得一批


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

long long n, ans = 1;

inline bool is_prime(long long x)
{
if(x == 1) return false;
for(long long i = 2; i*i <= x; ++i)
if(x%i == 0) return false;
return true;
}

int main()
{
cin >> n;
if(is_prime(n)) return puts("3")&0;
for(long long i = 2; i <= n; ++i)
{
if(n%i == 0)
{
int cnt = 0;
while(n%i == 0)
{
n /= i;
cnt++;
}
ans *= cnt*2+1;
if(is_prime(n))
{
ans *= 3;
break;
}
}
}
cout << ans << endl;
return 0;
}
求抱养
0%