首页 > 其他 > 详细

hdu5175 gcd 求约数

时间:2015-03-03 21:55:02      阅读:293      评论:0      收藏:0      [点我收藏+]

题意:求满足条件GCD(N,M) = N XOR M的M的个数

 

sol:和uva那题挺像的。若gcd(a,b)=a xor b=c,则b=a-c

暴力枚举N的所有约数K,令M=NxorK,再判断gcd(N,M)是不是等于K。

 

暴力枚举约数时传统方法是O(N)的,会完蛋

有个O(sqrt(N))的方法:

性质:若n%i==0,则有n%(n/i)=0

 

hdu5175 gcd 求约数

原文:http://www.cnblogs.com/pdev/p/4311969.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!