글 읽기 - 2981 반례가 있나요?

rlaeogus890 5년 전 0

find_gcd 함수는 맞고

void print_gcds(LL a) 함수에서 틀리는 것 같은데

void print_gcds(LL a)는 a의 약수(1과 주어진수들 중 가장작은 수 보다 큰 것을 제외한) 를 출력합니다.

뭐가 문제인가요?

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

typedef long long int LL;

LL find_gcd(LL a, LL b);
LL* arr;
void print_gcds(LL a);

int main()
{
	freopen("input.txt","r",stdin);
	int n;
	cin>>n;

	
	arr = new LL[n];

	for(int i=0; i<n; i++)
	{
		LL temp;
		cin>>temp;
		arr[i] = temp;
	}

	sort(arr,arr+n);

	if(n==2)
	{
		
		print_gcds( arr[1]-arr[0] );
	}
	else
	{

		

		LL gcd = arr[1]-arr[0];

		LL iter=2;
		
		for(; iter<n; iter++)
		{
			gcd = find_gcd( gcd, arr[iter]-arr[iter-1] );
			//cout<<"gcd is "<<gcd<<endl;
		}

		print_gcds(gcd);
	}
	// cout<<gcd;

	return 0;
}

LL find_gcd(LL a, LL b)
{
	LL r;
	while( a%b !=0 )
	{
		r= a%b;
		a=b;
		b=r;
	}
	return b;
}

void print_gcds(LL a)
{
	vector<LL> vec;
	
	for(int i=1; i*i<=a; i++)
	{
		if( a%i == 0 )
		{
			if(i != 1  &&  i<=(arr[0]))
			{
				vec.push_back(i);
			}
			if( i != a/i ) 
			{
				if(a/i != 1  &&  a/i<=(arr[0]))
					vec.push_back(a/i); 
			}
		}
	}

	sort(vec.begin(), vec.end());
	vector<LL>::iterator iter = vec.begin();

	for(iter ; iter!=(vec.end()); iter++)
	{
		
		
			cout<<*iter;

			if(iter+1 != vec.end())
			{
				cout<<" ";
			}
		

	}
	



}

zlzmsrhak 5년 전 4

네. 반례가 있습니다. 반례를 보시면 어떤것이 틀렸는지 바로 아실 것 같습니다.

2
2 10

정답:
2 4 8

출력:
2

rlaeogus890 5년 전 2

감사합니다. 최솟값보다 작아야한다는 편견 때문에 틀렸네요

86번 줄 && a/i<=(arr[0]) 제거하고 바로 통과했습니다.

jakeehoson 3년 전 0

감사합니다 저도 해결했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2981 반례가 있나요?

rlaeogus890 5년 전 0

zlzmsrhak 5년 전 4

rlaeogus890 5년 전 2

jakeehoson 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말