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

发表评论

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

你是机器人吗? =。= *