现在的位置: 首页 > 综合 > 正文

hdu 3501

2016年10月18日 ⁄ 综合 ⁄ 共 697字 ⁄ 字号 评论关闭

 http://acm.hdu.edu.cn/showproblem.php?pid=3501

 一道数学题,不是很难,老题了。但从中学到了不少东西。

    1:if gcd(n,i) == 1     then gcd(n,n-i) == 1

           so sum(n) = n * phi(n) / 2;  //sum(n): 比n小的和n互质的数的和   phi(n): 比n小的跟n互质的数的个数

 

    2:n = P1^n1 * P2^n2 * P3^n3 *…………* Pk^nk   //P1,P2,Pk都是比n小的质数

         而phi(n) = (P1-1)P1^n1 * (P2-1)P2^n2 *…………* (Pk-1)Pk^nk

         实际上phi(n) 可以用欧拉函数求出!

 

抱歉!评论已关闭.