D.Power Products(质因子)



题意:n个数ai,求有多少对ai相乘之后能变成某数的k次方的形式。
可以想到某数的k次方可以表示成多种质因子的k次方的乘积(例:6^3 = 2^3 * 3^3 ),
进一步想,如果对于每个ai我们都按照因子从小到大(不用管质不质因子了,即我们按照同一套分离方法分离所有ai)将 他表示成多个因子的乘积,
如果两个ai乘起来能表达成多个因子的k次方乘积,那么这两个ai分离出的每个因子都是相等的,且每个因子分离出的次数相加等于k。

那么我们就把每个ai分离的情况记录下来,这里怎么记录要灵活运用stl,
int main()
{
	ll ans = 0;
	int n, k;rd(n),rd(k);
	map<vector<pair<int, int>>, int> cnt;
	while (n--)
	{
		int a;rd(a);
		vector<pair<int, int>> now, nnow;
		for (int jd = 2; jd * jd <= a; jd++)
		{
			int cnt_jd = 0;
			while (a % jd == 0)
				cnt_jd = (cnt_jd + 1) % k,a /= jd;
			if (cnt_jd)
				now.push_back({jd, cnt_jd});
		}
		if (a > 1)//如果a还有剩余这里就是一次方
			now.push_back({a, 1});
		for (pair<int, int> z : now)
			nnow.push_back({z.first, k - z.second});
		ans += cnt[nnow];//能和这个数凑对的个数
		cnt[now]++;
	}
	cout << ans;
	return 0;
}


全部评论

相关推荐

不愿透露姓名的神秘牛友
07-21 13:38
8月实习会变多吗现在还没找到实习该怎么办...回复的hr好少
码农索隆:3-4月就要开始找,基本上6月份就发offer,7月初已经开始暑期实习了。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务