๋ฌธ์
๋ชจ๋ ์๋ฆฌ๊ฐ 1๋ก๋ง ์ด๋ฃจ์ด์ ธ์๋ ๋ ์์ฐ์ A์ B๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋, A์ B์ ์ต๋ ๊ณต์ฝ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด, A๊ฐ 111์ด๊ณ , B๊ฐ 1111์ธ ๊ฒฝ์ฐ์ A์ B์ ์ต๋๊ณต์ฝ์๋ 1์ด๊ณ , A๊ฐ 111์ด๊ณ , B๊ฐ 111111์ธ ๊ฒฝ์ฐ์๋ ์ต๋๊ณต์ฝ์๊ฐ 111์ด๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ ์์ฐ์ A์ B๋ฅผ ์ด๋ฃจ๋ 1์ ๊ฐ์๊ฐ ์ฃผ์ด์ง๋ค. ์ ๋ ฅ๋๋ ์๋ 263๋ณด๋ค ์์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ A์ B์ ์ต๋๊ณต์ฝ์๋ฅผ ์ถ๋ ฅํ๋ค. ์ ๋ต์ ์ฒ๋ง ์๋ฆฌ๋ฅผ ๋์ง ์๋๋ค.
ํ์ด
์ฒ์์ ๋ฌธ์ ๋ฅผ ๋ณด๊ณ ๋ฌด์จ ๋ง์ธ์ง ํ์ฐธ์ ํค๋งธ์๋๋ฐ ๋จ์ํ ์ต๋๊ณต์ฝ์์ ์๋ฆฌ์๋งํผ 1์ ์ถ๋ ฅํ๋ ๋ฌธ์ ์์ต๋๋ค. ์๋ฅผ๋ค์ด A๊ฐ 4๊ณ B๊ฐ 6์ด๋ผ๋ฉด ์๋์ ๊ฐ์ด ๊ตฌ์ฑ๋ฉ๋๋ค. ์ด๋ ์ต๋๊ณต์ฝ์๋ B์์ A๋ฅผ ์ ์ธํ 11์ด ๋ฉ๋๋ค.
A = 1111
B = 1111_11
์กฐ๊ธ ๋ ๊ฐ๋จํ๊ฒ ์ดํด๋ณด๋ฉด A๊ฐ 3์ด๊ณ B๊ฐ 6์ด๋ผ๋ฉด ์๋์ ๊ฐ์ต๋๋ค.
A = 111
B = 111_111
์ด๋ฅผ ์กฐ๊ธ ์ผ๋ฐํํ๋ฉด ์๋์ ๊ฐ์๋ฐ์, ์ด๋ฅผ ํตํด ์ด๋์ ๋ ๊ท์น์ ์ฐพ์ ์ ์์ต๋๋ค.
A = 111;
B = 111_111;
gcd = 111;
A = 1111111;
B = 1111111_1111111_1111111;
gcd = 1111111;
๋ฐ๋ผ์ ์๋์ ๊ฐ์ ํ์ด๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์ต๋๋ค.
'๐ PS > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
boj-1916 (0) | 2022.08.24 |
---|---|
boj-2252 (0) | 2022.08.22 |
boj-1922 ๋คํธ์ํฌ ์ฐ๊ฒฐ (0) | 2022.07.19 |
boj-1744 ์ ๋ฌถ๊ธฐ (0) | 2022.07.15 |
boj-1300 K๋ฒ์งธ ์ (0) | 2022.07.14 |
๋๊ธ