1. 题目

传送门=￣ω￣=

2. 题解

wcnmlgb 刚刚写到一半不知道按到什么键了回退到上一页，写的全没了 wcnmlgb

个人觉得出题人就是个sb，既然区间左端都是 1，干嘛还要输入？

设 $f(d)$为 $gcd(x,y)==d$的数对个数，$g(d)$为 $gcd(x,y)\% d==0$的数对个数。

这两个函数有什么关系呢？

函数 $g(d)$只要满足 $gcd(x,y)$是 d 的倍数就行了，而 $f(d)$要满足 $gcd(x,y)==d$，所以其实 g 包含了 f。

具体是怎样的关系呢？

$g(d)=f(d\times 1)+f(d\times 2)+f(d\times 3)+…$

在本题中，正式且装逼地说，就是这个：

$g(n)=\sum\limits_{n|d}{f(d)}(d<=min(a,b))$

是不是很眼熟？我才不会告诉你我是从 boshi dalao 的博客里复制出来的╭(╯^╰)╮

这不就是莫比乌斯反演吗？虽然 n 和 d 掉了个个儿，那还不是老套路，反演的时候也掉个个儿就行了。

所以我们通过莫比乌斯反演公式可以得到：

$f(n)=\sum\limits_{n|d}{u(\frac{d}{n})g(d)}(d<=min(a,b))$

我们要求的就是 $f(k)$。

原问题是 $gcd(x,y)==k,x\in [1,a],y\in[1,b]$，我们为了方便计算，不妨把整个式子都除以 k，就得到了：

$gcd(x,y)==1,x\in [1,a/k],y\in[1,b/k]$

这样我们要求的就是 $f(1)$了，这样不需要判断 n 是否能整除 d。即：

$f(1)=\sum\ {u(d)g(d)}(d<=min(a,b))$

莫比乌斯函数 u 的值可以用线性筛求得，那函数 g 呢？

其实很简单。

$gcd(x,y)\% d==0$，那么 x,y 一定都是 d 的倍数。在区间 [1,lim] 中是 d 的倍数的数的个数是 floor(lim/d)，那么 x 的值有 floor(a/d) 种取法，y 的值有 floor(b/d) 种取法，所以乘法原理得到一共有 floor(a/d)×floor(b/d) 种取法，所以：

$g(d)=\frac{a}{d}\times \frac{b}{d}$

然后还有，问题中说了，x,y 和 y,x 算一种解法。所以我们统计一下 $x,y\in min(a,b)$的个数，最后答案减去这个数就行了。

那么问题就迎刃而解了。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL t,a,b,k,mu[100005]={0,1},p[100005],cnt,ans1,ans2;
bool book[100005];
int main()
{
    for(int i=2;i<=1e5;i++)
    {
        if(!book[i])mu[i]=-1,p[cnt++]=i;
        for(int j=0;j<cnt;j++)
        {
            if(p[j]*i>1e5)break;
            book[p[j]*i]=1;
            if(i%p[j]==0){mu[p[j]*i]=0;break;}
            mu[p[j]*i]=-mu[i];
        }
    }
    scanf("%d",&t);
    for(int tot=1;tot<=t;tot++)
    {
        scanf("%lld%lld%lld%lld%lld",&a,&a,&b,&b,&k),printf("Case %d: ",tot);
        if(!k){printf("0\n");continue;}
        if(ans1=ans2=0,a/=k,b/=k,a>b)swap(a,b);
        for(int i=1;i<=a;i++)ans1+=mu[i]*(a/i)*(b/i),ans2+=mu[i]*(a/i)*(a/i);
        printf("%lld\n",ans1-(ans2>>1));
    }
    return 0;
}