这两天刷了几个关于gcd的很类似的问题，总结一下：
BZOJ2818 1<=x<=n，1<=y<=n，求满足gcd(x,y)=质数的个数
BZOJ2190 1<=x<=n，1<=y<=n，求满足gcd(x,y)=1（x、y互质）的个数
BZOJ2301 a<=x<=b，c<=x<=d，求满足gcd(x,y)=k的个数
HDU1695 1<=x<=m，1<=y<=n，求满足gcd(x,y)=d的个数
BZOJ2005 1<=x<=m，1<=y<=n，求sum{gcd(x,y)}
---------------------------
Reference: http://quartergeek.com/eight-gcd-problems/
还有三个没刷= =
---------------------------
莫比乌斯反演
http://blog.csdn.net/acdreamers/article/details/8542292
原文：http://www.cnblogs.com/pdev/p/4103858.html