求LCM(a,b)=n的(a,b)的总对数(a<=b)

\(a={p_1} ^ {a_1} *{p_1} ^ {a_1} *..........*{p_n} ^ {a_n}\)
\(b={p_1} ^ {b_1} *{p_1} ^ {b_1} *..........*{p_n} ^ {b_n}\)
\(lcm(a,b)={p_1} ^ {max(a_1,b_1)} *{p_2} ^ {max(a_2,b_2)} *..........*{p_n} ^ {max(a_n,b_n)}=n\)
假定\(a<=b\)
所以对n进行质因数分解,计算出每个质因数的指数部分,比如其中一部分\({p_n}^k\)则说明\(max(a_n,b_n)=k\),那么如果\(a_n=k\),那么\(b_n\)有\(k+1\)种取值方法,同理如果\(b_n=k\),那么\(a_n\)有\(k+1\)种取值方法,那么对于这个质因数我们有\(2*(k+1)-1\)种取值方法,一开始\(ans=1\),对于每个质因数乘以其贡献,那么除了\(a=b=n\)的情况,其他都计算了两次,由于最后我们要的是\((a<=b)\)的方案数,那么\(ans=ans/2+1\)即可

上一篇:Beautiful numbers CodeForces - 55D


下一篇:Codeforces 1499D. The Number of Pairs(数学)