莫比乌斯函数完整定义的通俗表达:
1)莫比乌斯函数μ(n)的定义域是N
2)μ(1)=1
3)当n存在平方因子时,μ(n)=0
4)当n是素数或奇数个不同素数之积时,μ(n)=-1
5)当n是偶数个不同素数之积时,μ(n)=1
/* * [题意] * 给出n, m, p,求有多少对a, b满足gcd(a, b)的素因子个数<=p * (其中1<=a<=n, 1<=b<=m) * * [解法] * 设A(d):gcd(a, b)=d的有多少种 * 设B(j): gcd(a, b)是j的倍数的有多少种,易知B(j) = (n/j)*(m/j) * 则由容斥原理得:(注:不同行的μ是不相同的,μ为莫比乌斯函数) * A(1) = μ(1)*B(1) + μ(2)*B(2) + μ(3)*B(3) + ... + μ(p1*p2...)*B(p1*p2...) * A(2) = μ(1)*B(1*2) + μ(2)*B(2*2) + μ(3)*B(3*2) + ... + μ(p1*p2..)*B(p1*p2..*2) * ... * A(d) = μ(1)*B(1*d) + μ(2)*B(2*d) + μ(3)*B(3*d) + ... + μ(p1*p2..)*B(p1*p2..*d) * *--> ans = A(1)+A(2)+...+A(d) = F(1)*B(1) + F(2)*B(2) + ... + F(p1*p2..)*B(p1*p2..) * * 于是可以枚举公约数i{表示A(i)},利用筛法找出i的倍数j,i对B(j)的贡献系数为:F(j)+=μ(j/i) * 总之,求出B(j)的总贡献系数F(j)即可得答案:F(1)*B(1)+F(2)*B(2)+...+F(n)*B(n) * * 上面没有限制gcd的素因子个数,要限制其实不难,给系数加多一维即可: * F(d)(p)表示:素因子个数<=p时,对B(d)的贡献系数 * * [分块加速思想] * 你可以再纸上模拟一下: * 设d在[i, n/(n/i)]的区间上,则该区间内所有的n/d都是一样的 * */ #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define LL long long #define M 500005 #define N 19 //返回n中有多少个x因子 int cal(int n, int x) { int res = 0; do { ++res; n /= x; } while (n % x == 0); return res; } //备注:分块加速求解需要求前缀和 //F[i][j]: 表示素因子个数<=j条件下的莫比乌斯前缀和:μ(1)+μ(2)+...+μ(i) int F[M][N]; int num[M]; //num[i]: i中含有多少个素因子 int h[M]; //h[i]: -1表示存在平方因子,否则表示有多少种素因子 //莫比乌斯函数的定义 int mob(int n) { if (h[n] == -1) return 0; //存在平方因子时,μ(n)=0 if (h[n] & 1) return -1; //奇数个不同素数之积,μ(n)=-1 return 1; //偶数个不同素数之积,μ(n)=1 } int main() { int t, n, m, p, i, j; //筛法算出num[]以及h[] for (i = 2; i < M; i++) { if (num[i]) continue; for (j = i; j < M; j+=i) { int tp = cal(j, i); num[j] += tp; if (tp > 1) { //j中含有多个i,必然存在平方因子 h[j] = -1; } else if (h[j] >= 0) { ++h[j]; } } } //枚举i作为公因子,对B(j)的贡献值为:mob(j/i) for (i = 1; i < M; i++) { for (j = i; j < M; j+=i) { F[j][num[i]] += mob(j/i); } } //为了表示素因子数<=j的意义,求j的前缀和 for (i = 1; i < M; i++) { for (j = 1; j < N; j++) { F[i][j] += F[i][j-1]; } } //为了分组加速求解,求i的前缀和 for (i = 1; i < M; i++) { for (j = 0; j < N; j++) { F[i][j] += F[i-1][j]; } } scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &m, &p); LL ans = 0; if (p >= N) { ans = (LL)n*m; } else { if (n > m) { n ^= m; m ^= n; n ^= m; } for (i = 1; i <= n; i = j + 1) { j = min(n/(n/i), m/(m/i)); ans += ((LL)F[j][p]-F[i-1][p])*(n/i)*(m/i); } } printf("%I64d\n", ans); } return 0; }
相关推荐
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...
hdu1001解题报告
hdu 1574 passed sorce
【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
hdu2101AC代码
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...
HDU(Hangzhou Dianzi University)是国内外知名的在线编程竞赛平台,主要服务于ACM/ICPC(国际大学生程序设计竞赛)以及相关的算法训练。"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码...
根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。