第一篇题解

我们都知道$lcm(a, b) = \frac{a * b}{\gcd(a, b)}$

∴ $\frac{lcm(a, b)}{a} = \frac{\frac{a * b}{\gcd(a, b)}}{a} = \frac{b}{\gcd(a, b)}$

题目的意思就被我们转化成了求$\frac{b}{\gcd(a, b)}$的种类数

又∵b是一个确定的数

∴$\frac{b}{\gcd(a, b)}$的种类数就等于$\gcd(a, b)$的种类数

由于$a$的范围在$[1, 10^{18}]$范围内,所以$\gcd(a, b)$的种类数就等于b的因数个数。

因数个数就可以$O(\sqrt n)$求辣QwQ

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
40
// Sooke bless me.
// LJC00118 bless me.
#include<bits/stdc++.h>

#define INF 2147483647
#define ll long long

ll Inp(){
char c = getchar();
ll Neg = 1;
while(c < '0' || c > '9'){
if(c == '-')
Neg = -1;
c = getchar();
}
ll Sum = 0;
while(c >= '0' && c <= '9'){
Sum = ((Sum << 3) + (Sum << 1)) + c - '0';
c = getchar();
}
return Neg * Sum;
}

int main(){
ll n = Inp();
ll qn = sqrt(n);
ll Ans = 1;
for(ll i = 2; i <= qn; i++){
ll Cnt = 1;
while(n % i == 0){
n /= i;
Cnt++;
}
Ans *= Cnt;
}
if(n > 1){
Ans *= 2;
}
printf("%lld", Ans);
}

 评论