본문 바로가기

수학10

확장 유클리드 공부한 블로그 : https://viruz.tistory.com/entry/EEA Extended Euclidean algorithm 확장 유클리드 알고리즘(Extended Euclidean algorithm)은 이름에서 알 수 있듯 유클리드 알고리즘의 확장 버전이다. 기존 유클리드 알고리즘이 두 정수 $a$, $b$의 $GCD$만 구했다면, 확장 유클리드 알고리즘은.. viruz.tistory.com 다음과 같은 식을 선형 방정식이라고 한다. ax + by = c 여기서 정수해 x,y는 c가 gcd(a,b)로 나눠지는 경우 존재한다. gcd(a,b) = g라고 하고 ax + by = g의 값을 구하는 과정은 https://www.youtube.com/watch?v=PmwLXveLtqc참고. 유튜브 속 .. 2020. 5. 5.
BOJ 2472 - 체인점 (다익스트라, 좌표압축, 세그트리, 수학) https://www.acmicpc.net/problem/2472 이런 문제 3문제를 3시간안에 중학생이 푼다 최대 n개의 정점으로 이뤄진 무방향 가중치 그래프가 주어진다. (n> u >> v >> w; g[u].push_back({ v,w }); g[v].push_back({ u,w }); } memset(d, 0x3f, sizeof(d)); for (int i = 0; i query; while (query--) { int i; cin >> i; cout 2020. 4. 22.
2019-2020 ICPC, Asia Jakarta Regional - H. Twin Buildings(수학, 기하) https://codeforces.com/problemset/problem/1252/H 바로 전에 포스팅한 문제의 풀이와 유사 L*W로 표현되는 영역들이 주어진다. (L,W n; for (int i = 0; i > l >> w; if (l > w) swap(l, w); a[i] = { l,w }; temp = max(temp, l * w); temp = max(temp, l * w); } sort(a, a + n); for (int i = n - 1; i >= 0; i--) sf[i] = max(sf[i + 1], a[i].second); for (int i = 0; i < n; i++) { ll l, w; tie(l, w) = a[i]; ans = max(.. 2020. 4. 20.
cf #538 div2 C - Trailing Loves (소인수분해, 수학) https://codeforces.com/contest/1114/problem/C n! 에 어떤 소수가 몇개 들어있는지 로그시간에 파악하는 법 확인. 오버플로우를 피하기 위한 조건문 확인. 최대 1e18의 n과 최대 1e12의 b가 주어진다. n!을 b진법으로 표현했을 때 trailing zero의 수를 세라. (ex. 9800은 10진법으로 trailing zero가 두개 있다.) n!을 b로 몇번 나눌 수 있는지 구하면 된다. b를 소인수분해하여 p ^ x꼴의 인수들에 대해서, n!에 그 하나하나의 인수가 나오는 횟수들의 최소를 구하면 된다. n!에 어떤 소수 x가 몇 개 들어있는지 반환하는 함수 f를 이용해서 풀 수 있다. ll f(ll x) { ll ret = 0; ll t = x; x = 1; .. 2020. 4. 2.

티스토리툴바