HDU 1695 GCD

Here

题意

给你5个数$a,b,c,d,k$a,b,c,d,k，让你求符合$a\leq x \leq b,c\leq y \leq d,(x,y)=k$a≤x≤b,c≤y≤d,(x,y)=k的$x,y$x,y对数，这里$(1,2)$(1,2)和$(2,1)$(2,1)算一种。
你可以认为所有$test case$testcase的$a,c=1$a,c=1

解

又是板子题啦，开始推式子
*除法默认向下取整
假设$b\leq d$b≤d

$\sum\limits_{x=1}^{b}\sum\limits_{y=1}^{d}[gcd(x,y)==k]$x=1∑b​y=1∑d​[gcd(x,y)==k]

$\sum\limits_{x=1}^{\frac{b}{k}}\sum\limits_{y=1}^{\frac{d}{k}}[gcd(x,y)==1]$x=1∑kb​​y=1∑kd​​[gcd(x,y)==1]

$\sum\limits_{x=1}^{\frac{b}{k}}\sum\limits_{y=1}^{\frac{d}{k}}\sum\limits_{g|gcd(x,y)}μ(g)$x=1∑kb​​y=1∑kd​​g∣gcd(x,y)∑​μ(g)

$\sum\limits_{g=1}^{\frac{b}{k}}μ(g)\lfloor\frac{b}{kg}\rfloor\lfloor\frac{d}{kg}\rfloor$g=1∑kb​​μ(g)⌊kgb​⌋⌊kgd​⌋

这儿算出来的答案会有重复的，由于我们假设$b\leq d$b≤d，所以只要减去$\frac{\sum\limits_{g=1}^{\frac{b}{k}}μ(g)\lfloor\frac{b}{kg}\rfloor\lfloor\frac{b}{kg}\rfloor}{2}$2g=1∑kb​​μ(g)⌊kgb​⌋⌊kgb​⌋​就是答案了

Code 62MS

/****************************
* Author : 水娃             *
* Date : 2020-08-19-14.54.19*
****************************/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ll long long
#define debug(a) cout<<#a<<" is "<<a<<"\n"
#define ull unsigned long long
#define fi first
#define se second
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<int,ll>pil;
typedef pair<ll,ll>pll;
const ll mo=(ll)1e9+7;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
const int MAXN=2e5+100;
int now;
int mu[MAXN];
int pri[MAXN>>1];
bool vis[MAXN];
void pre()
{
    now=0;
    mu[1]=1;
    for(int i=2;i<MAXN;i++)
    {
        if(!vis[i])
        {
            pri[++now]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=now&&i*pri[j]<MAXN;j++)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j])
            {
                mu[i*pri[j]]=-mu[i];
            }
            else
            {
                mu[i*pri[j]]=0;
                break;
            }
        }
    }
}
int cas;
void work()
{
    ll a,b,c,d,k;
    cin>>a>>b>>c>>d>>k;
    if(k==0)
    {
        cout<<"Case "<<++cas<<": "<<0<<"\n";
        return ;
    }
    if(b>d)swap(b,d);
    ll ans=0,top=b/k;
    for(int g=1;g<=top;g++)
    {
        ans+=mu[g]*(b/(k*g))*(d/(k*g));
    }
    ll ans1=0;
    for(int g=1;g<=top;g++)
    {
        ans1+=mu[g]*(b/(k*g))*(b/(k*g));
    }
    cout<<"Case "<<++cas<<": "<<ans-ans1/2<<"\n";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    pre();
    int T;cin>>T;while(T--)
        work();
    return 0;
}