专栏首页数据结构与算法BZOJ1101: [POI2007]Zap(莫比乌斯反演)

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

Description

  FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a ,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。

Input

  第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个 正整数,分别为a,b,d。(1<=d<=a,b<=50000)

Output

  对于每组询问,输出到输出文件zap.out一个正整数,表示满足条件的整数对数。

Sample Input

2 4 5 2 6 4 3

Sample Output

3 2 //对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有( 6,3),(3,3)。

HINT

Source

莫比乌斯反演裸题

\frac{n}{k}只有sqrt(n)个取值

所以可以用分块优化

#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;
int vis[MAXN];
long long prime[MAXN],mu[MAXN],tot=0;
void GetMu()
{
    vis[1]=1;mu[1]=1;
    for(int i=1;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];
}
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    N=1e5;
    GetMu();
    int QWQ=read();
    while(QWQ--)
    {
        int n=read(),m=read(),k=read();
        long long ans=0;
        int limit=min(n/k,m/k);
        int nxt=0;
        for(int i=1;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);
        printf("%lld\n",ans);
    }
    return 0;
} 

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ2820: YY的GCD(反演)

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

    attack
  • 线性筛莫比乌斯函数

    1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath...

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

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

    attack
  • BZOJ2820: YY的GCD(反演)

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

    attack
  • 线性筛莫比乌斯函数

    1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath...

    attack
  • 数学--图论--莫比乌斯线性筛模板

    风骨散人Chiam
  • 洛谷P2522 [HAOI2011]Problem b(莫比乌斯反演)

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

    attack
  • 【PAT甲级】1002 A+B for Polynomials (25分)

    This time, you are supposed to find A+B where A and B are two polynomials.

    韩旭051
  • 暑假(补)-6

    优先队列是什么呢?优先队列其实是一种特殊的队列,对队列的元素按照一定的先后顺序,队列自动排序,这就是优先队列。

    AngelNH
  • 洛谷2017 5月月赛R1

    我只想说面对这种难度的题目就是冲着20%的数据暴力。。。 分数:40+20+36.1+38+0+19 T1 签到题 III 题目背景 pj组选手zzq近日学会了...

    attack

扫码关注云+社区

领取腾讯云代金券