专栏首页数据结构与算法洛谷P2522 [HAOI2011]Problem b(莫比乌斯反演)

洛谷P2522 [HAOI2011]Problem b(莫比乌斯反演)

题目描述

对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。

输入输出格式

输入格式:

第一行一个整数n,接下来n行每行五个整数,分别表示a、b、c、d、k

输出格式:

共n行,每行一个整数表示满足要求的数对(x,y)的个数

输入输出样例

输入样例#1

2
2 5 1 5 1
1 5 1 5 2

输出样例#1:

14
3

说明

100%的数据满足:1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000

莫比乌斯反演

首先你要会求\sum ^{n}_{i=1}\sum ^{m}_{i=1}\left[ \gcd \left( i,j\right) = 1\right]

然后不难发现这题可以容斥处理

假设work(i,j)=\sum ^{n}_{i=1}\sum ^{m}_{i=1}\left[ \gcd \left( i,j\right) = 1\right]

那么ans=work(b,d)-work(a-1,d)-work(c-1,b)+work(a-1,c-1)

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int N,a,b,c,d,k,ans;
int vis[MAXN],prime[MAXN],mu[MAXN],tot=0;
void GetMu()
{
    vis[1]=1;mu[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!vis[i]) prime[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
            else mu[i*prime[j]]=-mu[i];
        }
    }
    
    for(int i=1;i<=N;i++) 
        mu[i]+=mu[i-1];
}
int work(int n,int m)
{
    int limit=min(n/k,m/k),ans=0;
    for(int i=1,nxt;i<=limit;i=nxt+1)
    {
        nxt=min(n/(n/i),m/(m/i));
        ans+=(mu[nxt]-mu[i-1])*(n/(k*i))*(m/(k*i));
    }
    return ans;
}
main()
{
    N=1e5;
    GetMu();
    int QWQ=read();
    while(QWQ--)
    {
        a=read(),b=read(),c=read(),d=read(),k=read();
        ans=work(b,d)-work(a-1,d)-work(c-1,b)+work(a-1,c-1);
        printf("%d\n",ans);        
    }
    return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ1101: [POI2007]Zap(莫比乌斯反演)

    Description   FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a ,y<=b,并且gc...

    attack
  • AtCoder Beginner Contest 103

    首先我们发现,对于每个$a_i$,我们都可以构造一个数使得$x \pmod {a_i} = a_i - 1$

    attack
  • HDU 4786Fibonacci Tree(最小生成树)

    Problem Description   Coach Pang is interested in Fibonacci numbers while Un...

    attack
  • BZOJ1101: [POI2007]Zap(莫比乌斯反演)

    Description   FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a ,y<=b,并且gc...

    attack
  • 图的基本算法实现(邻接矩阵与邻接表两种方法)

    ==========================================================

    阳光岛主
  • 【算法】关于图论中的最小生成树(Minimum Spanning Tree)详解

    这里的图当然不是我们日常说的图片或者地图。通常情况下,我们把图看成是一种由“顶点”和“边”组成的抽象网络。在各个“顶点“间可以由”边“连接起来,使两个顶点间相互...

    短短的路走走停停
  • BZOJ2820: YY的GCD(反演)

    \[\sum_{i = 1}^n \frac{n}{k} \frac{n}{k} \sum_{p \in P, p | k} \mu(\frac{K}{p})\...

    attack
  • 05:最大值和最小值的差

    05:最大值和最小值的差 总时间限制:1000ms内存限制:65536kB描述 输出一个整数序列中最大的数和最小的数的差。 输入第一行为M,表示整数个数,整数个...

    attack
  • HDU 1866 A + B forever!

    A + B forever! Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/3...

    ShenduCC
  • C++中的stack类、QT中的QStack类

    C++中的stack 实现一种先进后出的数据结构,是一个模板类. 头文件 #include<stack> 用法(以int型为例): stack <int> s;...

    张诺谦

扫码关注云+社区

领取腾讯云代金券