【三元组暴力】CF867 div3 G1

╰半夏微凉° 2024-03-22 09:10 62阅读 0赞

**赛后两分钟过题，难蚌**

[Problem - G1 - Codeforces][]

题意：

![95cc6cdd92f94bbb8cedf8f8664589de.png][]

思路：

很经典的统计三元组个数

一般都是去枚举中间那个

这个也可以枚举最后那个元素，枚举这个元素的因子，然后组合计数mp\[u/it\]\*mp\[u/it/it\]

**但是有个问题，可能会重复，即三元组可能会变成二元组**

**那么特判那个会重复的情况**

即 因子为1的情况特别计数

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    map<int,int> mp;
    
    int n;
    int c[mxn];
    
    int C3(int x){
    	return x*(x-1)*(x-2)/6;
    }
    void solve(){
    	mp.clear();
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>c[i],mp[c[i]]++; 
    	int ans=0;
    	for(int i=1;i<=n;i++){
    		int u=c[i];
    		set<int> S; 
    		for(int j=2;j<=u/j;j++){
    			if(u%j==0){
    				S.insert(j);
    				if(j!=u/j) S.insert(u/j);
    			}
    		}
    		for(auto it:S){
    			//if(mp.count(u/it)&&mp.count(u/it/it)) cout<<u<<" "<<u/it<<" "<<u/it/it<<'\n';
    			if(u%it==0&&(u/it)%it==0) ans+=mp[u/it]*mp[u/it/it];
    		}
    	}
    	//cout<<ans<<'\n';
    	for(auto it:mp){
    		if(it.second>=3){
    			ans+=C3(it.second)*6;
    		}
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	int __=1;cin>>__;
    	//p_init(1e7);
    	while(__--)solve();return 0;
    }

[Problem - G1 - Codeforces]: https://codeforces.com/contest/1822/problem/G1
[95cc6cdd92f94bbb8cedf8f8664589de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/73408ef0110f46afbebf017aef83607f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，62人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF713div3 F

[Problem - F - Codeforces][] 题意：小明想买一个价值为c的东西，他开始打工，他一开始在第i个职务，每天可以挣a\[i\]，他也可以用一天的时间

你的名字/ 2024年03月27日 16:20/ 0 赞/ 95 阅读

相关 Day 3 CF731div3 vp

这场我不好说，我感觉我是逆天，div3的C题都卡了很久，想太复杂了，一直wa2，结果没发现这么简单，越打越低能了属于是： ![2af077fd2c7a6f7e1123533c

今天药忘吃喽~/ 2024年03月27日 13:56/ 0 赞/ 79 阅读

相关【bitmask】CF731div3 D

这道题赛后秒了，是个结论（感觉也不算，因为非常好推）感觉这种序列+bitmask就是把这个序列想象成一个01矩阵，横向是30位的bit，纵向是n个数，这样感觉会好想一点，如

谁践踏了优雅/ 2024年03月27日 13:53/ 0 赞/ 100 阅读

相关 Day2 CF713 div3 vp A-G

[Dashboard - Codeforces Round \713 (Div. 3) - Codeforces][Dashboard - Codeforces Round _

深碍√TFBOYSˉ_/ 2024年03月27日 11:26/ 0 赞/ 76 阅读

相关 Day1 CF847 div3 vp A-E

[Dashboard - Codeforces Round \847 (Div. 3) - Codeforces][Dashboard - Codeforces Round _

川长思鸟来/ 2024年03月27日 10:50/ 0 赞/ 88 阅读

相关 CF756div3 vp

又被薄纱了，rk就不放了，好丢人QwQ [Dashboard - Codeforces Round 756 (Div. 3) - Codeforces][Dashboard

た入场券/ 2024年03月26日 18:42/ 0 赞/ 76 阅读

相关 20230304 CF855 div3 vp

[Dashboard - Codeforces Round 855 (Div. 3) - Codeforces][Dashboard - Codeforces Round 85

比眉伴天荒/ 2024年03月26日 17:41/ 0 赞/ 84 阅读

相关【sorting+暴力】CF624div3 C. Perform the Combo

[Problem - C - Codeforces][] 题意：给定一个字符串s和一个数列a，遍历数列a，每次操作都会给字符串前缀的前ai个的元素出现次数++，问你所有操

ゝ一世哀愁。/ 2024年03月22日 14:21/ 0 赞/ 71 阅读

相关【三元组暴力】CF867 div3 G1

赛后两分钟过题，难蚌 [Problem - G1 - Codeforces][] 题意： ![95cc6cdd92f94bbb8cedf8f8664589de.png][

╰半夏微凉°/ 2024年03月22日 09:10/ 0 赞/ 63 阅读

相关 CF #406 div1 ABC

[http://www.bilibili.com/video/av9365298/][http_www.bilibili.com_video_av9365298] [htt

待我称王封你为后i/ 2022年06月13日 08:43/ 0 赞/ 158 阅读