BZOJ2045: 双亲数

时间:2022-09-03 15:46:36

2045: 双亲数

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 602  Solved: 275
[Submit][Status]

Description

小D是一名数学爱好者,他对数字的着迷到了疯狂的程度。

我们以d = gcd(a, b)表示a、b的最大公约数,小D执著的认为,这样亲密的关系足可以用双亲来描述,此时,我们称有序数对(a, b)为d的双亲数。

与正常双亲不太相同的是,对于同一个d,他的双亲太多了 >_<

比如,(4, 6), (6, 4), (2, 100)都是2的双亲数。

于是一个这样的问题摆在眼前,对于0 < a <= A, 0 < b <= B,有多少有序数对(a, b)是d的双亲数?

Input

输入文件只有一行,三个正整数A、B、d (d <= A, B),意义如题所示。

Output

输出一行一个整数,给出满足条件的双亲数的个数。

Sample Input

5 5 2

Sample Output

3

【样例解释】

满足条件的三对双亲数为(2, 2) (2, 4) (4, 2)

HINT

对于100%的数据满足0 < A, B < 10^ 6

Source

第一届“NOIer”全国竞赛

题解:

POI ZAP的弱化版,不用分块,线性筛+枚举即可。

代码:

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 1000000+1000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline ll read()

 {

     ll x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }
ll n,m,d,mx,tot,mu[maxn],p[maxn];
bool check[maxn]; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read();m=read();d=read();n/=d;m/=d;
mu[]=;mx=min(n,m);
for2(i,,mx)
{
if(!check[i]){p[++tot]=i;mu[i]=-;}
for1(j,tot)
{
int k=i*p[j];
if(k>mx)break;
check[k]=;
if(i%p[j]==){mu[k]=;break;}
else mu[k]=-mu[i];
}
}
ll ans=;
for1(i,mx)ans+=mu[i]*(n/i)*(m/i);
printf("%lld\n",ans); return ; }

BZOJ2045: 双亲数的更多相关文章

  1. &lbrack;BZOJ2045&rsqb;双亲数(莫比乌斯反演)

    双亲数 Time Limit: 10 Sec  Memory Limit: 259 MBSubmit: 959  Solved: 455[Submit][Status][Discuss] Descri ...

  2. 【BZOJ2045】双亲数 莫比乌斯反演

    [BZOJ2045]双亲数 Description 小D是一名数学爱好者,他对数字的着迷到了疯狂的程度. 我们以d = gcd(a, b)表示a.b的最大公约数,小D执著的认为,这样亲密的关系足可以用 ...

  3. bzoj 2045&colon; 双亲数

    2045: 双亲数 Description 小D是一名数学爱好者,他对数字的着迷到了疯狂的程度. 我们以d = gcd(a, b)表示a.b的最大公约数,小D执著的认为,这样亲密的关系足可以用双亲来描 ...

  4. 【题解】Luogu P4450 双亲数

    原题传送门 这题需要运用莫比乌斯反演(懵逼钨丝繁衍) 设F(t)表示满足gcd(x,y)%t=0的数对个数,f(t)表示满足gcd(x,y)=t的数对个数,实际上答案就是f(d) 这就满足莫比乌斯反演 ...

  5. P4450 双亲数

    思路 同zap-queries 莫比乌斯反演的板子 数据范围小到不用整除分块... 代码 #include <cstdio> #include <algorithm> #inc ...

  6. JZYZOJ 1375 双亲数 莫比乌斯反演

    http://172.20.6.3/Problem_Show.asp?id=1375 网上搜推理图. 有一段没有写莫比乌斯反演都快忘了..数学能力--,定理完全不会推,但是这道题整体来说应该是比较好写 ...

  7. 洛谷 - P4450 - 双亲数 - 整除分块

    https://www.luogu.org/fe/problem/P4450 应该不分块也可以. 求\(F(n,m,d)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^ ...

  8. &lbrack;P4450&rsqb; 双亲数 - 莫比乌斯反演&comma;整除分块

    模板题-- \[\sum\limits_{i=1}^a\sum\limits_{j=1}^b[(i,j)=k] = \sum\limits_{i=1}^a\sum\limits_{j=1}^b[k|i ...

  9. LGOJ4450 双亲数

    Description link \[\sum \limits_{i = 1}^A \sum \limits_{j = 1}^B [ \gcd(i, j) = d] \] 要\(O(\sqrt n)\ ...

随机推荐

  1. &lbrack;译&rsqb;为什么我要离开gulp和grunt转投npm脚本的怀抱

    原文链接:https://medium.freecodecamp.com/why-i-left-gulp-and-grunt-for-npm-scripts-3d6853dd22b8#.n7m1855 ...

  2. tcpproxy:基于 Swoole 实现的 TCP 数据包转发工具的方法

    假设我们希望有一台机器A(ip 192.168.1.101)要开放端口6379给用户访问,但可能实际情况是用户无法直接访问到A(ip 192.168.1.101), 但却有一台机器B(ip 192.1 ...

  3. Linux下Postfix的配置和使用

    Postfix为何物,详见:http://zh.wikipedia.org/wiki/Postfix 0.关于Postfix postfix的产生是为了替代传统的sendmail.相较于sendmai ...

  4. 生成mif文件的几种方法总结

    mif文件就是存储器初始化文件,即memory initialization file,用来配置RAM或ROM中的数据.生成QuartusII11.0可用的mif文件,有如下几种方式: 方法1:利用Q ...

  5. 《细说PHP》的php语言结构

    6.1流程控制 顺序结构 语句按照出现的先后次序自上而下依次执行 分支结构 先做判断再做选择 6.3.4 特殊的流程控制语句 break语句结束当前for.foreach.while.do-while ...

  6. npm常用命令及版本号浅析

    npm 包管理器的常用命令 测试环境为node>=8.1.3&&npm>=5.0.3 1, 首先是安装命令 //全局安装 npm install 模块名 -g //本地安装 ...

  7. 【重学计算机】操作系统D5章:文件系统

    1. 文件系统 文件系统概述 文件的组织: 逻辑结构:流式.记录式 物理结构:顺序.连接.直接.索引 文件的存取:顺序.直接.索引 文件的控制:逻辑控制.物理控制 文件的使用:打开.关闭.读.写.控制 ...

  8. HDU 5963&lpar;游戏 博弈&plus;规律&rpar;

    题意是: 一群男生和一群女生玩游戏:给出一棵 n 个节点的树,这棵树的每条边有一个权值 0 或 1. 在一局游戏开始时,确定一个节点作为根.从女生开始,双方轮流进行操作. 当一方操作时,要先选择一个不 ...

  9. 文献--A Survey on Server-side Approaches to Securing Web Applications

    Q:1.如何定义XSS攻击? 2.taint-based 啥意思? 3. second-order vulnerabilities 啥意思?

  10. kibana多台服务部署

    nohup /usr/share/kibana/bin/kibana -c /etc/kibana/kibana5602.yml & cp kibana.yml kibana5602.yml ...