洛谷 P5150 题解

题面

因为 n=lcm(a,b)n = lcm(a, b)n=lcm(a,b) ，可以得出：

• a  和 b  的质因数都是 n 的质因数
• 对于 n  的每个质因数 x ，在 n 中的次数为 y ，那么 x  在 a 和 b  中至少有一个次数为 y，在另一个中的次数 <=y。

所以我们只要把 n 的每个质因数的次数求出来就好了

即ans=(2a1+1)×(2a2+1)×……×(2an+1)。

#include <iostream>#include <cmath>#pragma GCC optimize(2)using namespace std;void fenjie(long long n){    ;    ;i<=sqrt(n);i++)    {        )        {            ;            )            {                n/=i;                cnt++;            }            ans*=(*cnt+);        }    }    ) ans*=;    cout<<ans;}int main (){    long long n;    cin>>n;    fenjie(n);}