为什么不问问神奇海螺呢
为什么不问问神奇海螺呢
全部文章
数论之Mobi...
2018暑假组队赛记录(1)
ACM_心情(6)
codeforces2018(7)
DFS/BFS搜索(10)
Linux-Ubuntu(1)
python(1)
STL(12)
二分搜索(9)
健身(2)
几何之凸包问题(10)
几何之半平面交(6)
几何之旋转卡壳(2)
几何之模拟退火(5)
几何之面积问题(9)
几何技巧(7)
几何问题非模板问题(5)
动态规划之基础DP(54)
动态规划之状态压缩(1)
图论之二分图(5)
图论之强联通SCC(5)
图论之网络流(8)
套题(2)
学习(10)
学习资料(28)
年月问题(3)
思维(47)
括号匹配(2)
数学之博弈(6)
数据结构之Manacher(2)
数据结构之单调队列(1)
数据结构之字典树(3)
数据结构之字符串匹配KMP(4)
数据结构之并查集(10)
数据结构之生成树(3)
数据结构之线段树/树状数组(11)
数据结构之莫队算法(1)
数论之Nim博弈及变形(2)
数论之伯努利数(1)
数论之佩尔方程(4)
数论之因数相关(1)
数论之数学期望(2)
数论之组合数学(8)
数论之质数相关(1)
数论之进制转换(1)
暴力题(14)
未归档(37)
构造题(3)
模拟(9)
模板集合(打印)(9)
玄学黑科技(1)
生活分享(2)
电影(2)
算法学习(18)
自然溢出(1)
规律(7)
读书(7)
读书笔记(7)
贪心(21)
随机or玄学(1)
高精度(1)
归档
标签
去牛客网
登录
/
注册
Conchpeng
贵在坚持
全部文章
/ 数论之Mobius莫比乌斯反演
(共6篇)
[HAOI2011]Problem b [Mobius]
题意: 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。 100%的数据满足:1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000 思路: 是之前做的求(1,...
2018-10-08
0
487
Mophues HDU - 4746 [Mobius]
Mophues HDU - 4746 题意:[1,n] 和 [1,m]中有多少对数的GCD k,k的素因子个数小于等于p 思路: 我们先解决[1,n],[1,m]有多少对数的GCD为k 分析到这一步,复杂度为 q * n, 不能接受,考虑到在连续的k内(n/k) (m/k)是有重复部分...
2018-10-06
0
548
GuGuFishtion HDU - 6390 [Mobius]
GuGuFishtion HDU - 6390 思路: 从原式到第一个等式,神奇操作....... 当作结论用. 爆int了.难受 当然可以再优化复杂度到 #include<bits/stdc++.h> using namespace std; typedef l...
2018-10-05
0
497
Code HDU - 5212[Mobius]
Code HDU - 5212 题意: 给定长为n的数组A, a[i]<=1e4 思路:有如下定义 f(n)为gcd==n的对数 F(n)为gcd是n倍数的对数 Accepted 5212 124MS ...
2018-10-04
0
512
TrickGCD HDU - 6053 [Mobius]
TrickGCD HDU - 6053 题意: 求存在多少个数组b,使得b[i]>=a[i] && gcd(b[1]...b[n])>=2 思路: 求出所有gcd是1倍数的方案数x 求出所有gcd是1的方案数y ans=x-y 经过系列化简...
2018-10-03
0
462
GCD HDU - 1695 [3种做法]
GCD HDU - 1695 题意:求[1,n],[1,m]中,GCD(i,j)==k的方案数 思路: 有三种做法 1.等价求GCD(i,j)==1在区间[1,n/k],[1,m/k]的方案数O(q*n) 62ms 2.在1的基础上,分块 O(q*sqrt(n)); 15ms 3...
2018-10-02
0
466