首页 > 其他分享 >CF1007B 题解

CF1007B 题解

时间:2024-06-06 12:00:27浏览次数:18  
标签:bc int 题解 CF1007B fa fb fc id

CF1007B

思路

显然题目要求计数 \(u\mid A,v\mid B,w\mid C\)。\(O(n\sqrt n)\) 预处理出每个数的所有因数,记为集合 \(p_i\)。

容斥,记集合 \(a,b,c,ab,ac,bc,all\) 为 \(p_A,p_B,p_C,p_A\cap p_B,p_A\cap p_A,p_B\cap p_C,p_A\cap p_B\cap p_C\)。可以用 bitset 维护交集。

首先加上 \(|a||b||c|\)。

  • \(u\in a,v\in bc,w\in bc,v\neq w\)。\(u,v\) 可以交换,最开始多算 \(1\) 次,减去。

  • \(u\in abc,v\in abc,u\neq v,w\in bc\setminus all\)。最开始算 \(4\) 次,第一步减 \(4\) 次,加上 \(1\) 次。

  • \(u\in ab,v\in bc,w\in ac\)。最开始算两次,减去 \(1\) 次。

  • \(u,v,w\in all,u=v\neq w\)。最开始算 \(3\) 次,第一步减 \(3\) 次,加上 \(1\) 次。

  • \(u,v,w\in all\),\(u,v,w\) 互不相等。最开始算 \(6\) 次,第一步减 \(3\times 3\) 次,加上 \(4\) 次。

观察到 \(2^3\times 3^3\times 5\times 7\times 11=83160\),所以 \(|p_i|\le 128\)。如果把分解因数写成先分解质因数再 dfs 求因数,复杂度 \(O(n)\),常数约为 \(400\)。

code

long long  a,b,c,ans;
vector<int> p[maxn];
int gcd(int a,int b){
	if(a%b==0)return b;
	return gcd(b,a%b);
}
int id[maxn],tim;
bitset<385> fa,fb,fc;
void work(){
	a=read();b=read();c=read();ans=0;
	fa.reset(),fb.reset(),fc.reset();
	for(int i:p[a])id[i]=0;
	for(int i:p[b])id[i]=0;
	for(int i:p[c])id[i]=0;
	tim=0;
	for(int i:p[a])if(!id[i])id[i]=++tim;
	for(int i:p[b])if(!id[i])id[i]=++tim;
	for(int i:p[c])if(!id[i])id[i]=++tim;
	for(int i:p[a])fa[id[i]]=1;
	for(int i:p[b])fb[id[i]]=1;
	for(int i:p[c])fc[id[i]]=1;
	long long ab=(fa&fb).count(),ac=(fa&fc).count(),bc=(fb&fc).count(),all=(fa&fb&fc).count();
	a=p[a].size(),b=p[b].size(),c=p[c].size();
	// cout<<a*b*c<<" "<<a*bc*(bc-1)/2<<" "<<b*ac*(ac-1)/2<<" "<<c*ab*(ab-1)/2<<" "<<all*(all-1)<<" "<<all*(all-1)*(all-2)/6<<"\n";
	ans=a*b*c-a*bc*(bc-1)/2-b*ac*(ac-1)/2-c*ab*(ab-1)/2+all*(all-1)+4*all*(all-1)*(all-2)/6;
	ans+=all*(all-1)/2*(ab-all)+all*(all-1)/2*(ac-all)+all*(all-1)/2*(bc-all);
	ans-=(ab-all)*(bc-all)*(ac-all);
	printf("%lld\n",ans);
}
int pre[maxn],cnt;
bool vis[maxn];
int f[maxn];
void s(int n){
	for(int i=2;i<=maxn-10;i++){
		if(!vis[i])pre[++cnt]=i,f[i]=i;
		for(int j=1;j<=cnt&&i*pre[j]<=n;j++){
			vis[i*pre[j]]=1;f[i*pre[j]]=pre[j];
			if(i%pre[j]==0)break;
		}
	}
}
vector<pii> val;
void dfs(int dep,int mul,int idx){
	if(dep==val.size()){
		p[idx].push_back(mul);
		return ;
	}
	for(int i=0,s=1;i<=val[dep].se;i++){
		dfs(dep+1,mul*s,idx);
		s*=val[dep].fi;
	}
}
int T;
signed main(){
	T=read();s(maxn-10);
	for(int i=1;i<=maxn-10;i++){
		int x=i;val.clear();
		while(x>1){
			int lst=f[x],num=0;
			while(f[x]==lst){
				++num;
				x/=f[x];
			}
			val.push_back({lst,num});
		}
		dfs(0,1,i);
	}
	while(T--)work();
}

标签:bc,int,题解,CF1007B,fa,fb,fc,id
From: https://www.cnblogs.com/yhddd/p/18234877

相关文章

  • 【面试宝藏】MySQL 面试题解析
    MySQL面试题解析1.数据库三大范式是什么?第一范式(1NF):确保每列的原子性,即每列不能再分。第二范式(2NF):在满足1NF的基础上,每个非主属性完全依赖于主键,即消除部分依赖。第三范式(3NF):在满足2NF的基础上,任何非主属性不依赖于其他非主属性,即消除传递依赖。2.MySQL有关权限......
  • 【面试宝藏】Redis 常见面试题解析其二
    Redis高级面试题解析20.说说Redis哈希槽的机制?Redis集群采用哈希槽(HashSlot)机制来分布和管理数据。整个哈希空间被划分为16384个槽,每个键通过CRC16校验后取模映射到一个哈希槽。每个节点负责一部分哈希槽,从而实现数据分片和负载均衡。21.Redis集群的主从复制......
  • P4785 [BalticOI 2016 Day2] 交换 题解
    看到\(i\)和\(\lfloor\frac{i}{2}\rfloor\),考虑一颗二叉树。题目的操作相当于按顺序交换当前节点和左右儿子的权值。假设当前考虑的节点为\(id\),左儿子为\(ls\),右儿子为\(rs\),当前这些点的值分别为\(A,B,C\)。因为\(id\)的位置最靠前,最终又要字典序最小,所以要尽可能......
  • 题解:SP1442 CHAIN - Strange Food Chain
    双倍经验:P2024[NOI2001]食物链思路:一眼鉴定为并查集。观察题目发现有三种状态,考虑使用种类并查集(又称扩展域并查集)。既然有三种状态那么种类并查集自然也要开三倍。CODE:#include<bits/stdc++.h>usingnamespacestd;intfa[150010];intGet_Find(intx){//寻找父节点......
  • P1654 OSU! 题解
    P1654OSU!题解题目链接好题!但不得不说早期洛谷的题解质量是真的差,感觉没有一篇题解是讲的特别清楚的,我看了好久才搞懂。下面是我认为的一种更规范的解题过程。首先,我们设随机变量\(X_i\)表示从\(i\)向左的极长1串的长度,并且对于任意的\(i\),我们要想办法求出\(E(X_i......
  • (第26天)【leetcode题解】226、翻转二叉树 589、N叉树的前序遍历 590、N叉树的后序遍
    目录226、翻转二叉树题目描述思路代码589、N叉树的前序遍历题目描述思路代码590、N叉树的后序遍历题目描述思路代码思考总结226、翻转二叉树题目描述给你一棵二叉树的根节点root,翻转这棵二叉树,并返回其根节点。示例:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,......
  • Codeforces Round 949题解(A、B、C)
    A.TurtleandPiggyArePlayingaGame首先\(p\)选\(2\)的话除得最慢,得的分多。考虑二进制表示,如果\(x=(1000000000)_{bin}\),则每次除以\(2\)都是相当于右移一位,除完之后仍然是\(2\)的倍数,变成\(1\)的步数就是把最高位的\(1\)移动到\(0\)位的步数。因为\(2l\ler\),所以\(l......
  • P8125 [BalticOI 2021 Day2] The short shank 题解
    首先会发现若\(t_i<=T\)的话那么他最终一定会造反。我们只考虑\(t_i>T\)的情况。设\(lst_i\)表示\(i\)左边第一个可以影响(使他造反)到\(i\)的位置,那么我们一定要在\([lst_i,i]\)这个区间中的某一个位置放上床垫才能使\(i\)不造反。这样有一个\(O(nd)\)的dp,但......
  • 2024年03月 GESP等级认证Python编程(一级)试题解析
    【单选题】(每题2分)1、小杨的父母最近刚刚给他买了一块华为手表,他说手表上跑的是鸿蒙,这个鸿蒙是?()A、小程序   B、计时器   C、操作系统   D、神话人物   正确答案:C2、中国计算机学会(CCF)在2024年1月27日的颁奖典礼上颁布了王选奖,王选先生的重大贡献是?()A、制......
  • Codeforces Round 950 (Div. 3)个人题解(A~F1)
    CodeforcesRound950(Div.3)个人题解(A~F1)题解火车头#define_CRT_SECURE_NO_WARNINGS1#include<iostream>#include<vector>#include<algorithm>#include<set>#include<unordered_map>#include<cstring>#include<cstdio&......