「codechefSUBGCD」Subarray GCD

2014年9月24日3,3880

题解

发现如果一段子序列的gcd=1的话那么整段的gcd也等于1

。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<set>
#define ll long long
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int gcd(int x,int y)
{
	return y==0?x:gcd(y,x%y);
}
int T,n,ans;
int main()
{
	T=read();
	while(T--)
	{
		n=read();ans=read();
		for(int i=1;i<n;i++)
		{
			int x=read();
			ans=gcd(ans,x);
		}
		if(ans==1)printf("%d\n",n);
		else puts("-1");
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<set>

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int gcd(int x,int y)

{

return y==0?x:gcd(y,x%y);

}

int T,n,ans;

int main()

{

T=read();

while(T--)

{

n=read();ans=read();

for(int i=1;i<n;i++)

{

int x=read();

ans=gcd(ans,x);

}

if(ans==1)printf("%d\n",n);

else puts("-1");

}

return 0;

}

« 「BZOJ1876」[SDOI2009] SuperGCD 「考后欢乐赛」最小公倍数 »

hzwer.com _ Home | http://hzwer.com

「codechefSUBGCD」Subarray GCD

分类目录

热门文章

Myfriends

近期评论