题意:对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数
思路:在hdu1695的基础上加上容斥,即:ans=solve(b/k,d/k)-solve((a-1)/k,d/k)-solve((c-1)/k,b/k)+solve((a-1)/k,(c-1)/k),详见代码:
/*********************************************************
file name: bzoj2301.cpp
author : kereo
create time: 2015年02月17日 星期二 10时46分33秒
*********************************************************/
#include<iostream>
#include<c......
阅读全文