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 条评论
登录 后参与评论

相关文章

来自专栏拭心的安卓进阶之路

Android 框架学习2:源码分析 EventBus 3.0 如何实现事件总线

Go beyond yourself rather than beyond others. 上篇文章 深入理解 EventBus 3.0 之使用篇 我们了解了 ...

52750
来自专栏数据结构与算法

洛谷P1351 联合权值(树形dp)

10220
来自专栏ACM小冰成长之路

UVA-11600-Masud Rana

ACM模版 描述 ? ? 题解 image.png ? 保存六位小数…… 代码 #include <cstdio> #include <cstring> #in...

23960
来自专栏数据结构与算法

BZOJ1576: [Usaco2009 Jan]安全路经Travel(最短路 并查集)

给你一张无向图,保证从1号点到每个点的最短路唯一。对于每个点求出删掉号点到它的最短路上的最后一条边(就是这条路径上与他自己相连的那条边)后1号点到它的最短路的长...

8710
来自专栏小灰灰

Greenrobot-EventBus源码学习(四)

EventBus 深入学习四之实例&类说明 本篇开始,则转向greenrobot/EventBus, 之前基本上将Guava中设计的思路捋了一遍,逻辑比较简...

48090
来自专栏数据结构与算法

洛谷P2763 试题库问题(最大流)

10130
来自专栏数据结构与算法

BZOJ4919: [Lydsy1706月赛]大根堆(set启发式合并)

不是链的时候直接当链做,每个节点维护一个multiset表示计算LIS过程中的单调栈

19910
来自专栏数据结构与算法

洛谷P1709 [USACO5.5]隐藏口令Hidden Password(最小表示法)

13230
来自专栏数据结构与算法

Educational Codeforces Round 42 (Rated for Div. 2)

9920
来自专栏数据结构与算法

关于scanf与cin哪个快的问题

一开始入c++的时候成天跑cin,cout 直到有一天用cin,cout超时 才知道scanf比cin快的多 但是后来又听说加了ios::sync_with_s...

409120

扫码关注云+社区

领取腾讯云代金券