9267 A+B 풀이 - PS 마이너 갤러리

알고리즘 문제를 해결하는 Problem Solving을 다루는 갤러리입니다.

매니저

캐티(tae826)

부매니저

하루룽(ailedear) Gravekper(gravekpe…) 옥토끼(moonrabb…) 나는최고(mebest)

개설일

2018-05-28

[풀이] 9267 A+B 풀이앱에서 작성

Bubbler

2024.05.10 18:03:22

조회 400 추천 7 댓글 3

https://discord.com/channels/857583541440348170/1116766234298552493/1204332800820518922

Discord - A New Way to Chat with Friends & Communities

Discord is the easiest way to communicate over voice, video, and text. Chat, hang out, and stay close with your friends and communities.

discord.com

위 링크는 예전에 다른 분이랑 풀이 간략하게 얘기했던 디코 메시지 링크고, 아래에는 좀 더 정리된 풀이가 있으니 스포 싫으면 뒤로가기 ㄱ

ax+by=s, x,y>0, gcd(x,y)=1을 만족하는 x y가 있으면 yes 아니면 no다.

gcd(a,b)=1이라고 가정, egcd 등을 써서 kab+ca+db=s, 0<=c<b, 0<=d<a를 만족하는 k, c, d를 구할 수 있다. k가 음수면 불가능

이제 가능한 x,y의 값은 x=c+kb-ib, y=d+ia로 나타낼 수 있다. 0<=i<=k

그럼 이제 gcd(x,y)=gcd(c+kb-ib, d+ia)

= gcd(ib+(-c-kb), ia+d)

여기서 i의 계수를 줄이는 방향으로 유클리드 알고리즘을 실행할 수 있음을 깨닫는 것이 중요함. 그러면 최종적으로 어떤 수 X와 Y에 대해 gcd(i+X,Y)의 형태가 된다.

이제 답이 no가 나오려면 범위 내의 모든 i에 대해 저 gcd가 1이 아니어야 함, 즉 Y가 k+1개의 연속한 정수와 서로소가 아니어야 함.

이때 Y와 서로소가 아닌 연속한 수가 그렇게 많지 않을 것이라는 직관이 있으면 그냥 코드를 짜서 맞을 수 있다. 좀더 그럴듯한 근거를 대자면 Jacobsthal function이라는 게 있다. J(n)은 k개의 연속한 정수가 n과 서로소가 아닐때 k의 최대값으로 정의함. 논문을 조금 뒤져보면 J(197#)=642라는 값을 찾을 수 있고, 197# (primorial; 197 이하의 소수들의 곱)은 대략 10^80 정도 됨. Y가 아무리 커져도 그거보단 작을 거라고 확신할 수 있고, 따라서 i를 0부터 대입해보면 대략 642번 안에 서로소인 쌍을 찾을 수 있을 거라고 볼 수 있음.

- dc official App

고정닉 3

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	말머리	제목	글쓴이	작성일	조회	추천
2928	설문	연예인하면 더 인기 많을 것 같은 스포츠 스타는?	운영자	24/09/16	-	-
48765	일반	그러고 보니 피갤컵 배경 언제 들어와 [3]	고추꺼내봐	09.11	312	2
48764	구인	혹시 대회 검수 도와줄 사람 있을까 [10]	머야	09.11	834	6
48763	일반	역방향 다익스트라 벽느꼈다 [3]	ㅇㅇ	09.11	388	0
48762	질문	time보다 memory가 중요한 분야가 머머 있음? [13]	ㅇㅇ	09.11	414	2
48761	질문	유니온파인드에 스플릿 연산을 추가할 순 없음? [8]	ㅇㅇ	09.11	321	0
48759	일반	ㄷㄷ화성지도 재채점으로 0ms에서 시간초과됐네 [3]	ㅇㅇ	09.11	380	2
48758	일반	내가 P갤 와서 는 것 [3]	ㅇㅇ(222.112)	09.11	377	6
48757	일기	사실 설명글이 한국어를 못하거나 읽는사람이 한국어를 못하거나 [1]	ㅇㅇ	09.11	235	1
48755	일반	백준형 갑자기 열심히 일하는거 적응안되네 [3]	ㅇㅇ(118.235)	09.11	749	14
48754	일반	icpc 본선 날짜 실화냐 시발 [8]	ㅇㅇ(58.140)	09.11	545	2
48752	일반	Dp 설명 저만 헷갈리나요? [9]	ㅇㅇ(106.101)	09.10	403	0
48750	질문	피린이 방향성 한 번 봐주실수 있나요?(고민상담) [7]	ㅇㅇ(211.234)	09.10	427	4
48749	일반	기여 다른 건 모르겠고 그런 건 있으면 좋겠음 [4]	ㅇㅇ(182.210)	09.10	325	0
48748	일반	기여 난이도가 정확하게 나오려면	ㅇㅇ(222.112)	09.10	505	14
48746	일기	4년동안의 PS 기록 [9]	아름드리나무	09.10	1298	47
48743	일반	치킨을 케이크처럼 쉽게 먹는법 [3]	ㅇㅇ(61.40)	09.10	251	0
48741	일반	이분탐색은 왜 뜬금없이 쓰이는게 많을까 [2]	ㅇㅇ(175.204)	09.10	291	1
48740	일반	티어가 중요함? [1]	ㅇㅇ(218.48)	09.10	342	8
48739	일반	Ps라는게 참 오묘하네 [8]	ㅇㅇ(149.88)	09.10	483	2
48738	일반	기여가 참 쉽지 않긴 함	ㅇㅇ(223.39)	09.10	152	2
48737	일반	남 기여하는데 왜지랄임 [2]	ㅇㅇ(39.7)	09.10	858	25
48736	일반	백준 2277 금고털기 이거 뭔 문젠지 아는 사람 있냐 [1]	ㅇㅇ(223.33)	09.10	234	0
48735	질문	외판원 순회(백준 2098) 도저히 못풀겠음 [5]	ㅇㅇ(106.101)	09.10	304	0
48734	일반	아무리생각해도 내가 더 합리적이고 티어 좀 내려쳐도 [14]	ㅇㅇ	09.10	594	5
48733	일반	고려대는 어떤곳일까	ㅇㅇ(14.46)	09.10	345	0
48732	일반	선생님들 길이보단 시간이 절대적이죠? [9]	ㅇㅇ(125.242)	09.10	362	3
48731	일반	소신기여하는 사람에게 바라는 점 [9]	ㅇㅇ(106.101)	09.10	960	33
48730	일반	최단거리랑 루트 찾는거 간단하게 어케함? [2]	ㅇㅇ(118.235)	09.10	253	0
48729	일반	맞왜틀 시발 [2]	ㅇㅇ(118.91)	09.10	132	1
48728	일반	2025년 좆된점 ㅋㅋ [4]	ㅇㅇ(223.39)	09.10	464	8
48727	질문	뉴비 4949번 질문점 [2]	ㅇㅇ(116.32)	09.10	201	2
48726	일반	기여하는거 피곤해요 [10]	captain(118.235)	09.10	1079	30
48724	일반	루비5 문제를 길이 130B로 푸는건 대체 머냐ㄷㄷ [7]	ㅇㅇ(115.22)	09.10	695	1
48723	질문	cout cin endl공부하는데 질문 [4]	ㅇㅇ(121.167)	09.10	238	0
48722	일반	코드 복습에 대해 조언좀.. [6]	ㅇㅇ(125.184)	09.10	242	1
48721	일반	뭐가 틀린거지 [4]	ㅇㅇ(118.235)	09.09	354	0
48720	일반	LG 4번 루4 기여좀 [4]	ㅇㅇ(223.39)	09.09	968	23
48719	일반	여기 저같은 분 없나요 [1]	ㅇㅇ(106.102)	09.09	334	1
48718	일반	Ps보다 이산수학 코딩하는게 더 재밌지 않냐 [12]	ㅇㅇ(106.102)	09.09	507	0
48717	일반	아무도 안풀만한 적당히어려운 기하문제풀고 루1기여 [4]	ㅇㅇ(118.91)	09.09	498	5
48716	일반	요즘 게임도 재미없네 [2]	ㅇㅇ(116.32)	09.09	276	0
48715	일반	1초에 계산 횟수 10^8이 국룰 아니었음? [8]	ㅇㅇ(59.29)	09.09	540	0
48714	일반	브루트포스 문제 항상 볼때마다 [2]	ㅇㅇ(49.142)	09.09	243	2
48713	일반	Lgcpc 본선 마지막 문제 어케품? [5]	ㅇㅇ(182.231)	09.09	350	0
48712	일반	피갤은 디코 잼민이 못버팀	ㅇㅇ(14.46)	09.09	300	0
48711	질문	vscode c++ 설정 [4]	ㅇㅇ(61.81)	09.09	286	0
48710	일반	이문제 예제 왜 답이 이거임? [2]	ㅇㅇ(118.235)	09.09	309	0
48709	일반	슬슬 피갤 vs 디코로 한판 떠도 될거같으면 개추 [4]	ㅇㅇ(223.39)	09.09	543	8
48707	일반	LGCPC 본선 출제 후기 [8]	benedict0724(175.127)	09.09	923	32
48706	일반	백준이터진건 첨보네 거의 [1]	ㅇㅇ	09.09	330	0