当前位置：首页 > article >正文

洛谷P2651 添加括号III

article 2025/3/6 9:24:29

题目链接：P2651 添加括号III - 洛谷 | 计算机科学教育新生态

题目难度:普及一

题目分析：

a1肯定是分子，a2肯定是分母，那么尽可能多的是a3以后的变为分子，怎么办呢？

a1/(a2/a3/a4/...)=a1a3a4.../a2，所以我们只要确认a1a3a4.../a2是否是整数。

但是如果进行约分，知道a2能被约分成1，那么就是整数。

每次将a2=a2/gcd(a2,ai),i=(1,3,4,5...)即可。

代码部分：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10010;
int t,n;
int a[N];

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

int read()
{
	int s=0,f=1;char ch=getchar();
	
	while (ch<'0'||ch>'9')
	{
   	   if (ch=='-') f=-1;
	   ch=getchar();
	}
	while (ch>='0'&&ch<='9')
	{
	   s=s*10+ch-'0';
	   ch=getchar();
	}
	return s*f;
}

void sol()
{
   n = read();
   a[1] = read(),a[2] = read();
   a[2] /= gcd(a[1],a[2]);
   
   for(int i = 3; i <= n; i++)
   {
   	 a[i] = read();
   	 a[2] /= gcd(a[2],a[i]);
   }
   if(a[2] == 1) puts("Yes");
   else puts("No");
}

int main() {
   
    t = read();
    
    while(t--) sol();
    
    return 0;
}

查看全文

原文地址:https://blog.csdn.net/2302_79431881/article/details/145408419
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.kler.cn/a/527287.html 如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！