第一篇题解
我们都知道lcm(a,b)=gcd(a,b)a∗b
∴ alcm(a,b)=agcd(a,b)a∗b=gcd(a,b)b
题目的意思就被我们转化成了求gcd(a,b)b的种类数
又∵b是一个确定的数
∴gcd(a,b)b的种类数就等于gcd(a,b)的种类数
由于a的范围在[1,1018]范围内，所以gcd(a,b)的种类数就等于b的因数个数。
因数个数就可以O(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
|
#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);
}
|
