Number_Theory

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/15309 🧐 관찰 및 접근 # 이진트리..는 아니고 삼각형이구나. 걍 좀 펴서 생각하면, 이항계수처럼 생각하면 되는 것 같다. $i$번째 줄은 $(Ax + B)^i$ 의 계수처럼 생각하면 되는듯? 아 근데 그 뭐냐 겹치게 하면 안되는구나 특정 삼각형은 그 초항만 생각하면 되는것같으니까, $m$개의 행을 포함하는 정삼각형을 어떻게 계산할지 생각해보자. 대충 로그정도에 계산하면 되는데.. 일단 초항이 1일때 식은 뭐랑 같지? $1 + (A+B) + (A^2 + AB + B^2) + \cdots$ 같은 느낌인건데… 어차피 행 자체에는 누적합 맛으로 할 수 있겠네. 어라? 이건 그냥 윗 행에다가 $A$를 곱하고, $B^N$만 더하면 될거같은딩. 대충 해버리죠? 아니 잠깐만!!!!!!!!! $m$이 $10^{18}$이다!! 비상!!!!!!!!! 로그가 붙을만한곳은 분할정복 거듭제곱같은거밖에 없는데… 아 잠깐만. 이거 그냥 그 유명한 고딩때 그 공식처럼 $(A-B)$곱하면 정리되는 꼴 아닌가? 그러면 $(A-B) + (A^2 - B^2) + (A^3 - B^3) + \cdots$ 이건 $(A + A^2 + \cdots + A^m) - (B + B^2 + \cdots + B^m)$이자나! $\frac{A^{m+1} - 1}{A-1} - \frac{B^{m+1} - 1}{B-1}$ 로 계산할 수 있을 것 같고, 이걸 $A-B$로 나눠서 끝내자. 아!! $A = B$인 경우를 조심해야할 것 같고, $A = 1$이나 $B = 1$인경우도 조심해야할 것 같다. $A = B$라면? $1 + 2A + 3A^2 + \cdots + mA^{m-1}$ 를 구해야하는데, 저 합을 $S$라고 하자. 그러면 $AS - S = 1 + A + A^2 + \cdots + A^m$ 니까, $A = 1$인 경우 말고는 이걸 구해서 $A-1$로 나누면 될 것 같은데? 케이스 처리를 조심하자. 💻 풀이 # 코드 (C++): void solve(){ mint A, B; cin >> A >> B; int Q; cin >> Q; while(Q--){ ll x, y, m; cin >> x >> y >> m; x--; y--; mint cho = 1; cho *= A.pow(x-y); cho *= B.pow(y); mint trig = 0; if(A == B){ if(A == 1) trig = mint(m)*(m+1)/2; else trig = (A.pow(m+1) - 1) / (A - 1).pow(2); } else{ if(A == 1) trig += m; else trig += (A.pow(m+1) - 1) / (A - 1) - 1; if(B == 1) trig -= m; else trig -= (B.pow(m+1) - 1) / (B - 1) - 1; trig /= (A-B); } cout << cho * trig << '\n'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34088 🧐 관찰 및 접근 # $K$로 나눈 나머지가 같다 = 고른 부분집합의 원소들의 차이가 모두 $K$의 배수이다. 그러면? 분위기상 소수만? 신경써도 되는거같다. 근데 숫자들의 차이가 $10^9$까지인데… 그러면 너무 많은데 흠 근데 일단 직관적으로, $K = 2$일때 비둘기집의 원리에 의해 답은 ${N/2}$ 이상이긴 하다. 그리고 직관적으로, 웬만한 경우에 $K$가 작을때 답이 있을 것 같다. $K$가 클때를 억지로 만들 수 있나? $K > 1000$ 쯤듸는 어떤 소수라고 하면, 억지로 만들 수 있는 것 같긴 하다. 그런데, 이때 $K$가 $N/2$개 이상의 부분집합에 대해 나머지가 같아야하므로, 다르게 말하면 어떤 두 수를 뽑앗을때 50% 이상의 확률로 $K$는 해당 수의 약수이다. 랜덤으로 풀 수 있지 않을까? 💻 풀이 # 코드 (C++): void solve(){ auto start = chrono::high_resolution_clock::now(); bitset<32000> isPrime; isPrime.set(); isPrime[0] = isPrime[1] = 0; rep(i, 2, 32000) if(isPrime[i]){ for(ll j = (ll)i*i; j < 32000; j += i) isPrime[j] = 0; } vector<int> primes; rep(i, 2, 32000) if(isPrime[i]) primes.push_back(i); int N; cin >> N; vector<ll> A(N); rep(i, 0, N) cin >> A[i]; int ans = (N+1)/2; while(1){ auto end = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::milliseconds>(end - start); if(duration.count() > 900) break; int a = rand() % N, b = rand() % N; int diff = abs(A[a] - A[b]); vector<int> divs; for(int p: primes){ if(p*p > diff) break; if(diff % p == 0){ divs.push_back(p); while(diff % p == 0) diff /= p; } } if(diff > 1) divs.push_back(diff); for(int d: divs){ map<int, int> mp; for(auto x: A) mp[x%d]++; for(auto [_, c]: mp) ans = max(ans, c); } } cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/25229 번역 번역 # 문제 # 방향이 없는 간선으로 이루어진 트리가 있으며, 각 노드는 정수 값을 가지고 있습니다. 인접한 두 노드의 값의 최대공약수(GCD)가 $1$보다 엄밀히 클 때, 이 두 노드를 **GCD-조화롭다(GCD-harmonic)**고 합니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30449 🧐 관찰 및 접근 # $R(n)$의 길이는 몇일까? $R(1) = 2$이고, $R(k) = R(k-1) + k$와 서로소인 자연수의 개수 인 것 같다. 오일러 피함수의 부분합 개수랑 같다. 암튼 나이브하게 돌려보니, 7600459개가 나온다. 이걸 0.5초안에 이걸 정렬하고 찾을?수?있을까? ㅋㅋ 수열이 좌우로 대칭인걸 고려하면 380만개정도만 정렬해도 될거같긴 한데… 그래도 빡세보인다. 0.5초라서 흠.. 답에 대한 이분탐색이 될까? 사실 깔끔하게 이분탐색 하기 위해선, 정수조건으로 바꾸려면 1~5000의 LCM을 구해야 한다.. 진짜 개에바 $10^{-4}$에 대한 정밀도까지만 하면 되지 않을까? 해봤자 가장 작은 수는 $\frac{1}{5000}$이니까… 라기엔 두 분수의 차는 결국 더 빡세지네. 해봤자 $\frac{1}{5000*4999}$인거같긴 한데… 아니 잠깐만, 생각해보니까 1~5000에 대해서 따로 정렬하면 시간복잡도가 꽤나 줄어드는것같다. 이렇게 해서 답에 대한 이분탐색을 해볼까..? 다 실패하고, nth_element와 short와 pragma Ofast와 Clang까지 섞은 최적화로 풀엇다… 하 이게 뭐하는 문제냐 ㄱ- 헉, 앞에 최대공약수를 구하는 부분을 반복문으로 전처리하면 훨씬 빠르게 돈다. 거기가 병목이었다니 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<pair<short,short>> v; v.reserve(N * N / 2); v.push_back({0, 1}); v.push_back({1, 1}); rep(i, 1, N+1) rep(j, i+1, N+1){ if(__gcd(i, j) != 1) continue; v.push_back({(short)i, (short)j}); } int sz = (int)v.size(); if(K*2 > sz){ K = sz - K + 1; nth_element(v.begin(), v.begin() + K - 1, v.end(), [](auto& a, auto& b){ return a.first * b.second > a.second * b.first; }); } else { nth_element(v.begin(), v.begin() + K - 1, v.end(), [](auto& a, auto& b){ return a.first * b.second < a.second * b.first; }); } cout << v[K-1].first << " " << v[K-1].second << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/12858 🧐 관찰 및 접근 # $\text{gcd}(n, n+1)$은 몇일까? $G = gcd(n, n+1)$이 어떤 소수 $p$를 약수로 가진다고 하자. 이때 $p$는 간격 $p$마다 한개씩 존재한다. $p = 2$면 $p$를 약수로 가진 수는 $2$칸마다 존재한다. 따라서 연속된 두 수는 어떤 공약수인 소수 $p$를 가질 수 없다! 따라서 $\text{gcd}(n, n+1) = 1$임을 알 수 있다. 같은 방법으로, $\text{gcd}(a, b) = \text{gcd}(a, b-a)$ 임도 알 수 있다. 유클리드 호제법에서도 알 수 있듯이! 구간 쿼리지만, Lazy하게 연산하기는 쉽지 않아보인다. 하지만 $\text{gcd}(x_a, x_{a+1}, x_{a+2}, \dots, x_b)$ 를 $\text{gcd}(x_a, x_{a+2} - x_{a+1}, x_{a+3} - x_{a+2}, \dots, x_b - x_{b-1})$ 이라고 생각하면, 바뀌는 수는 생각보다 많지 않다! Lazy한 합 연산과 최대공약수에 대한 그냥 세그먼트 트리로 풀 수 있지 않을까? 사실 Lazy부분도 구간 덧셈, 점 쿼리이므로 그냥 세그로 바꿀 수 있지만, 귀찮으니까 ㅋㅋ 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; LazySegmentTree LST(N); ST.init(N-1); vector<ll> A(N); rep(i, 0, N) cin >> A[i]; rep(i, 0, N) LST.set(i, A[i]); LST.build(); rep(i, 0, N-1) ST.set(i, abs(A[i+1] - A[i])); ST.build(); int Q; cin >> Q; while(Q--){ ll op, a, b; cin >> op >> a >> b; a--; b--; if(op){ LST.update(a, b, op); if(a-1 >= 0) ST.update(a-1, abs(LST.query(a-1, a-1) - LST.query(a, a))); if(a+1 < N) ST.update(a, abs(LST.query(a+1, a+1) - LST.query(a, a))); }else{ cout << gcd(LST.query(a, a), ST.query(a, b-1)) << '\n'; } } } 🔒 구현 코드 잠금