글 읽기 - 무엇이 문제일까요...

jindoldream 3년 전 0

다음과 같이 짰고 반례도 없어보이는데 왜 안될까요..

반례좀 찾아주시면 감사하겠습니다

#include<stdio.h>
#include<algorithm>

int lcm(int a, int b)
{ int k=a;
  while(k%b!=0)
  k=k+a;
  
  return k;
}

int gcd(int a, int b){

	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

int n;
int gap;
int gcdgap;
int a[11], b[11], p[11], q[11];
int ans[11];
int check[11]={};

int main()
{
scanf("%d", &n);
for(int i=1; i<=n-1; i++)
scanf("%d %d %d %d", &a[i], &b[i], &p[i], &q[i]);
gap=1;

for(int i=0; i<=n-1; i++)
ans[i]=1;

for(int i=1; i<=n-1; i++)
{ gap=lcm(lcm(gap, p[i]),q[i]);
}

gcdgap=gap;

ans[a[1]]=gap;
check[a[1]]=1;
for(int i=1; i<=n-1; i++)
{ if(i==1){ ans[b[1]]=(gap*q[1])/p[1];
check[b[1]]=1;
}
if(check[a[i]]!=1) 
{ans[a[i]]=(ans[b[i]]*p[i])/q[i];
check[a[i]]=1;}
else{
ans[b[i]]=(ans[a[i]]*q[i])/p[i];
check[b[i]]=1;
}
}



for(int i=0; i<=n-1; i++)
{ gcdgap=gcd(gcdgap, ans[i]);
}

for(int i=0; i<=n-1; i++)
{ans[i]/=gcdgap;
}

for(int i=0; i<=n-1; i++)
printf("%d ", ans[i]);
}

bansh123 3년 전 6

하 저도 진짜 반례도못찾겠고 왜안되는지 모르겠어서 구글링좀해봤는데

왜인진 잘 모르겠는데 최대공약수, 최소공배수 관련된 변수들 int말고 longlong으로 선언하니까 그냥되더라고요.... 아무리생각해도 int로 해도 n<10이라 오버플로우나 그런거 없을거같은데 참...

로직에 문제없는것같다면 longlong으로 선언바꿔보심을 추천합니다.

tmax7937 1년 전 0

진짜 왜그런건가요? 저는 자바인데 저도 long으로 바꾸니까 되네요. 설령 9를 9번 곱해도 integer 범위 안쪽인데..

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

문제

문제

출처

ICPC

무엇이 문제일까요...

jindoldream 3년 전 0

bansh123 3년 전 6

tmax7937 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말