题意:给定a,b,c,d,k
x属于[1 , c],y属于[1 , d],求满足gcd(x,y)=k的对数。其中<x,y>和<y,x>算相同。
解法一:不妨设c<d,x<=y。问题可以转化为x属于[1,c / k ],y属于[1,d/k ],x和y互质的对数。
那么假如y<=c/k,那么对数就是y从1到c/k欧拉函数的和。如果y>c/k,就只能从[ c/k+1 , d ]枚举,然后利用容斥。详见代码:
/*********************************************************
file name: hdu1695.cpp
author : kereo
create time: 2015年02月11日 星期三 18时0......
阅读全文