shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

全部文章 / 题解（共1篇）

破译密码来自专栏

这个题目和莫比乌斯反演并没有太大关系,只是用了莫比乌斯函数而已,本质就是整数分块+容斥原理.题目很简单:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d.这个怎么做呢?我们转化一下,就变成了x'=a/d,y'=b/d.并且gcd(x',y'...

莫比乌斯反演整数分块容斥原理

2020-07-01

2 724