Codeforces Round #518 (Div. 2) B LCM

时间:2023-03-09 17:53:33
Codeforces Round #518 (Div. 2) B LCM

传送门

https://www.cnblogs.com/violet-acmer/p/10163375.html

题解:

  这道题有点意思,有点数学的味道。

  根据定义“[a,b] / a”可得这求得是lcm(a,b) / a。

  转换一下:

  易知 gcd(a,b)= (a*b) / lcm(a,b) <=> lcm(a,b) = (a*b) / gcd(a,b)

  那么 lcm(a,b) / a <=> b / gcd(a,b)

  而gcd(a,b)不就是b的约数吗?

  因为 a 取的最大值为 1018  ;

  而 b 的最大值才为 1010 ;

  所以这道题直接转化为求 b 的约数个数了.

AC代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll __int64 ll b;
int Prime()
{
int res=;
int x=sqrt(b);
for(int i=;i <= x;++i)
{
if(b%i != )
continue;
res++;
if(b/i != i)
res++;
}
return (b == ? :res);
}
int main()
{
scanf("%I64d",&b);
printf("%d\n",Prime());
return ;
}