๋ฌธ์ ๋๋ณด๊ธฐํ์ด์ผ์ชฝ์์ ๋ถํฐ ์ ํํ ๊ฒฝ์ฐ ์ ํํ ์ ์๋ ์์์ ๊ฐ์๋ ⌊|S|/2⌋, ์ค๋ฅธ์ชฝ๋ถํฐ ์ ํํ ๊ฒฝ์ฐ ์ ํํ ์ ์๋ ์์์ ๊ฐ์๋ ⌈|S|/2⌉๋ก ์ ํด์ ธ ์๋ค.ํ ๋ฐฉํฅ์ ์ ํํ๊ฒ ๋๋ค๋ฉด ํด๋น ๋ฐฉํฅ์ ์์ ์ ์ฒด์ GCD๋ฅผ ์ ํํ๊ณ ๋จ์ ์์๋ค์์ ๋ค์ ๋ฐฉํฅ์ ์ ํํ๋ ํ์คํฌ๋ฅผ ์งํํ๊ฒ ๋๋ค.๊ทธ๋ฌ๋ฏ๋ก ์ผ์ชฝ์ ์ ํํ๋ ๊ฒฝ์ฐ, ์ค๋ฅธ์ชฝ์ ์ ํํ๋ ๊ฒฝ์ฐ์ ๋ํ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํด ์ต๋๊ฐ์ ๊ตฌํ๋ฉด ํ๋ฆฌ๋ ๋ฌธ์ ๋ค. ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 2*10^5์ด๊ณ , a๊ทธ๋ฌ๋ฏ๋ก ์ ์ฒด ๋ฐฐ์ด์ ๋ํด gcd ์ฐ์ฐ์ ํ๊ฒ ๋๋ ์ด ์๊ณ ๋ฆฌ์ฆ์ O(N log min(a, b))์ด๋ค.#include #include #include using namespace std;int N, arr[200001], ans;int gcd(int a, i..
