cf C.Collatz Conjecture
2021/11/7 23:14:21
本文主要是介绍cf C.Collatz Conjecture,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Dashboard - 2017 Benelux Algorithm Programming Contest (BAPC 17) - Codeforces
大意:给n个数字,求区间gcd的情况数
首先,设我们有三个数字 a b c
gcd(a,b)==d,gcd(b,c)==e,gcd(d,e)==f
因为gcd(b,b)==b,gcd(gcd(a,b),gcd(b,c))=gcd(a,b,c,d)=gcd(a,b,c)
所以我们可以把所有的区间gcd写成一个倒三角形,下面的是上面俩的gcd
9 6 2 4
3 2 2
1 2
1
去重完就只有9 6 4 3 2 1结果为6
完毕
怎么可能这么简单
留个伏笔,因为我也没搞清楚这个算法为啥能过
如果有某一行的很多个数字是一样的,他们gcd的值都是本身,和边上gcd的值也唯一,所以可以省略为一个
#include<bits/stdc++.h> using namespace std; #define int long long const int N=5e5+5; int ans[N]; int num[N]; int f1[N]; int f2[N]; int n,l=0; unordered_set<int> s; long long gcd(long long a,long long b) { if(b==0) return a; else return gcd(b,a%b); } signed main(){ std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++) { cin>>num[i]; s.insert(num[i]); } int t=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n-i+1-l;j++)// { if(i%2==1) { f1[j-t]=gcd(num[j],num[j+1]); if(f1[j-t]==f1[j-t-1]) { f1[j-t]=0;t++; } else { s.insert(f1[j-t]); } } else { num[j-t]=gcd(f1[j],f1[j+1]); if(num[j-t]==num[j-t-1]) { num[j-t]=0; t++; } else { s.insert(num[j-t]); } } } l+=t; t=0; } cout<<s.size()<<"\n"; }
这篇关于cf C.Collatz Conjecture的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!