初遇唯一分解定理

任意一个大于1的自然数N,如果N不是质数,那么它都能写成若干个素数相乘的形式,即:n=p1^e1*p2^e2*p3^e3*p4^e4...*pn^en;,而n的所有因子个数和=(1+e1)*(1+e2)*(1+e3)...*(1+en)

https://www.nowcoder.com/acm/contest/90/F

题目描述 :给定n,求1/x + 1/y = 1/n (x<=y)的解数。(x、y、n均为正整数)

由1/x+1/y = 1/n 可以变形为(x-n)*(y-n)= n^2  也就相当于找n^2得到所有因子个数和,由于n^2与n的质因子相同,所以n^2=p1^2e1*p2^2e2*.....pn^2en,也就是个数和=(1+2e1)*(1+2e2)*(1+2e3)*....*(1+2en) 而由于x<=y;所以最后结果应该是sum/2+1

解题步骤:1)转化等式,变成求所有因子和  2)利用唯一分解定理求因子个数和(即先找出所有的质因子(统计各质因子个数),再利用定理即可)

原文地址:https://www.cnblogs.com/MekakuCityActor/p/8653512.html