CF1025B Weakened Common Divisor 题解
2024-09-08 05:13:38
Content
定义 \(n\) 个数对 \((a_1,b_1),(a_2,b_2),(a_3,b_3),...,(a_n,b_n)\) 的 \(\text{WCD}\) 为能够整除每个数对中至少一个数的 \(>1\) 的整数。现在,给出 \(n\) 个数对,请找出它们的 \(\text{WCD}\),或者这 \(n\) 个数对没有符合要求的 \(\text{WCD}\)。
数据范围:\(1\leqslant n\leqslant 1.5\times 10^5,2\leqslant a_i,b_i\leqslant 2\times 10^9\)。
Solution
我们先把第一个数对的质因子分解出来,然后再在后面找是否有不能够满足条件的质因子,有的话就删除,否则就保留着。最后看是否还有剩下的质因子即可。
Code
int n, pr[150007];
int main() {
n = Rint;
F(i, 1, n) {
int x = Rint, y = Rint;
if(i == 1) {
F(j, 2, sqrt(x)) if(!(x % j)) {pr[++pr[0]] = j; while(!(x % j)) x /= j;}
if(x != 1) pr[++pr[0]] = x;
F(j, 2, sqrt(y)) if(!(y % j)) {pr[++pr[0]] = j; while(!(y % j)) y /= j;}
if(y != 1) pr[++pr[0]] = y;
} else F(j, 1, pr[0]) if(!pr[j]) continue; else if(x % pr[j] && y % pr[j]) pr[j] = 0;
}
F(i, 1, pr[0]) if(pr[i]) return printf("%d", pr[i]), 0;
printf("-1");
return 0;
}
最新文章
- linux服务器做网关
- 画图程序升级版Draw_v1
- 【UOJ #20】【NOIP 2014】解方程
- HDU 4267 A Simple Problem with Integers --树状数组
- bzoj2561
- 机器学习实战__安装python环境
- (3)选择元素——(15)总结(Summary)
- UVA 10594-Date Flow(无向图的最小费用网络流+题目给的数据有误)
- wordpress一些常用代码
- PHP命名空间(Namespace)的使用详解
- Java学习笔记10---访问权限修饰符如何控制成员变量、成员方法及类的访问范围
- 理解Python迭代对象、迭代器、生成器
- Scrapy基础(十四)————知乎模拟登陆
- JAVA创建子进程并处理waitFor() 阻塞问题
- day9-复习学习python实例
- IE6里样式表不起作用解决方法
- 连接APB1和APB2的设备有哪些
- CodeForces - 457C:Elections(三分)
- hdu5009 Paint Pearls[指针优化dp]
- Linux内核分析第三周——构造一个简单的Linux系统MenuOS
热门文章
- 论文翻译:2020_Densely connected neural network with dilated convolutions for real-time speech enhancement in the time domain
- Redis基本数据类型底层数据结构
- Debugging and Running MPI in Xcode
- 【百奥云GS专栏】全基因组选择之工具篇
- Excel-vlookup(查找值,区域范围,列序号,0)如何固定住列序列号,这样即使区域范围变动也不受影响
- mysql 索引的注意事项
- UE4 C++工程以Game模式启动
- Mybatis批量添加、更新小结
- 使用 Skywalking 对 Kubernetes(K8s)中的微服务进行监控
- C#序号