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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注