大致题意： 求\(\sum_{x=a}^b\sum_{y=c}^d[gcd(x,y)==k]\)。

关于另一道题目

在看这篇博客之前，如果你做过一道叫做的题目，那么此题就很简单了。

如果没做过，还是推荐你先去做一下吧。

解题思路

做完了上面提到的那题，或许对这题你就有一个很显然的想法了。

即差分。

其实，上面那题就是此题\(a=c=1\)的特殊版本。

因此，如果令\(ans_{i,j}=\sum_{x=1}^i\sum_{y=1}^j[gcd(x,y)==k]\)，则：

\[answer=ans_{b,d}-ans_{a-1,d}-ans_{b,c-1}+ans_{a-1,c-1}\]

于是就水过了（相当于双倍经验啊）。

代码

#include
    
     #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define uint unsigned int#define LL long long#define ull unsigned long long#define swap(x,y) (x^=y,y^=x,x^=y)#define abs(x) ((x)<0?-(x):(x))#define INF 1e9#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))#define ten(x) (((x)<<3)+((x)<<1))#define N 50000using namespace std;int X1,Y1,X2,Y2,k;class FIO{    private:        #define Fsize 100000        #define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)        #define pc(ch) (FoutSize