当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

HDU 4746 Mophues

发表于: 2013-10-01   作者:基德KID.1412   来源:转载   浏览:
摘要: 莫比乌斯函数完整定义的通俗表达: 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
莫比乌斯函数完整定义的通俗表达:
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 4746 Mophues

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2108 题意: 逆时针的给出N个点的坐标,求所围
http://acm.hdu.edu.cn/showproblem.php?pid=2501&PHPSESSID=fme1u1rdulrni3r4tbv5t5e186 递推分析
http://acm.hdu.edu.cn/showproblem.php?pid=4862 #include <iostream> #include <cstdio&
http://acm.hdu.edu.cn/showproblem.php?pid=3376 题意:一个矩阵,每个点有价值,起点左上角终点右
http://acm.hdu.edu.cn/showproblem.php?pid=3038 题意:[1-n]的区间,有m个询问,每个询问表示[a,b
http://acm.hdu.edu.cn/showproblem.php?pid=4861 两个人进行游戏,桌上有k个球,第i个球的值为1^i+
Baby Ming and Weight lifting Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536
HDU 1577 http://acm.hdu.edu.cn/showproblem.php?pid=1577 判断三点共线公式为:(x2-x1)*(y3-y1)=(
hdu 1016 Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768
Pleasant sheep and big big wolf Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号