정화 코딩

https://www.acmicpc.net/problem/13172 이 문제의 핵심을 정리하면 아래와 같다. 기약분수 a/b를 다음과 같이 하나의 정수로 표현할 수 있다.  이 때 X는 1,000,000,007과 같은 큰 소수이다.b^(-1)은 b의 모듈러 곱셈에 대한 역원인데, 다음과 같이 계산할 수 있다.  이 정도만 알면 문제를 풀 수 있다. 이제 구체적으로 어떻게 구현할지 생각해보자.한 줄에 분모와 분자 순서대로 한 쌍의 분수가 들어온다. 각 분수에 대해 a * b^(-1) mod X 를 구하면 된다. 그리고 모든 값들을 마치 확률을 더하듯 그냥 더해주면 된다.  내가 헷갈렸던 점은 기약분수 a/b에 대해서 저렇게 계산해야 된다고 하길래 들어온 분모와 분자에 대해서 우선 기약분수 형태로 만들어줘야..

https://www.acmicpc.net/problem/32649 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a, b, k; cin >> a >> b >> k; vector ans; ans.push_back(a); ans.push_back(b); for (int i = a + 1; i = k) { for (int i = 0; i 캐어려운 정수론 문제인줄 알았는데 그냥 브루트포스 문제였다 ㅎㅎ;;핵심 포인트는 d는 A의 배수이면서 B의 약수여야 한다는 것이다. 그런데 A와 B의 범위가 그렇게 ..

3회차 - n log n 정렬, 기초 수학   수 정렬하기 2 https://www.acmicpc.net/problem/2751C++ STL에 있는 정렬 함수를 사용한 풀이입니다. 정렬 함수를 사용하기 위해 헤더를 포함시켰습니다.#include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector a(n); for (int i = 0; i > a[i]; sort(a.begin(), a.end()); for (int i = 0; i   수 정렬하기 3https://www.acm..

https://www.acmicpc.net/problem/19699 #include #include #include #include using namespace std;bool p[10000];int n, m;vector h;vector chk;set ans;void dfs(int idx, int res) { if (idx == m) { if (res > n >> m; h = vector(n); chk = vector(n, false); for (int i = 0; i > h[i]; sort(h.begin(), h.end()); dfs(0, 0); if (ans.empty()) { cout 우선 에라토스테네스 체로 1부터 10000까지 범위에..

https://www.acmicpc.net/problem/25333 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { int a, b, x; cin >> a >> b >> x; vector chk(x + 1, false); queue q; q.push(0); chk[0] = true; int cnt = 0; while (!q.empty()) { i..

https://www.acmicpc.net/problem/17433 #include #include using namespace std;int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x % y);}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t, n; cin >> t; while (t--) { cin >> n; vector num(n); vector dif(n - 1); bool inf = true; for (int i = 0; i > num[i]; ..

https://www.acmicpc.net/problem/1684 #include #include #include using namespace std;int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x % y);}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector num(n); vector dif(n - 1); for (int i = 0; i > num[i]; if (i == 0) continue; dif[i - 1] = abs(num[i] - num[i -..

https://www.acmicpc.net/problem/21919 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector a = vector(n); for (int i = 0; i > a[i]; } int cnt = 0; long long ans = 1; for (int x: a) { //! bool isPrime = true; double tmp = sqrt(x); if (tmp * tmp == x) { ..