본문 바로가기

수학

BOJ)11560 다항식 게임 문제: icpc.me/11560 문제를 풀기 위하여 k:0~20 에 대한 p(x)를 모두 구하여도 시간내에 충분히 수행가능하다. 따라서 미리 계산을 다 해준 뒤 쿼리를 받을 때 마다 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;typedef long long ll;vector b, a;ll x, y, z;int main() { for (int i = 3; i 더보기
(pow(A,B))mod C 를 logB 시간안에 구하는 함수 http://jason9319.tistory.com/169 예전에 이항 계수를 구할 때 설명한 적이 있지만 빈번하게 사용되는 유용한 테크닉이라 생각되어 다시 설명드립니다. 우선 소스코드를 먼저 보시죠 12345678910111213141516#include #include using namespace std;typedef long long ll;ll a, b, c;ll mypow(ll x, ll y) { if (!y)return 1; if (y % 2) return (x*mypow(x, y - 1)) % c; return mypow((x * x) % c, y / 2) % c;}int main() { scanf("%lld%lld%lld", &a, &b, &c); printf("%lld", mypow(a, .. 더보기
BOJ)3049 다각형의 대각선 문제: icpc.me/3049 볼록 다각형에서의 대각선들의 교점을 구하는 문제이다. 볼록 다각형에서는 겹치는 교점은 존재하지 않으므로 교점이 생성 될 수 있는 경우인 다각형의 꼭지점이 4개일 때의 경우를 세주면 된다. 즉 nC4를 출력해주면 된다. 123456789#include #include using namespace std;int n;int main() { scanf("%d", &n); printf("%d\n", (n*(n - 1)*(n - 2)*(n - 3)) / 24); return 0;}Colored by Color Scriptercs 더보기
BOJ)6064 카잉 달력 문제: icpc.me/6064 n년도를 x:y로 표현할 때 n+1년도는 if(x==m) x=1 else x=x+1 if(y==n) y=1 else y=y+1 로 표현할 때 x:y가 몇년도인지 찾는 문제이다. 처음에 단순하게 시뮬레이션을 돌려봤으나 시간초과를 받아서 문제를 다시 보니 M과 N이 40000씩이므로 O(N*M)의 시뮬레이션으로는 해결할 수 없는 문제였다. 그래서 수식을 사용하여 for(int i=0;i 더보기
BOJ)1183 약속 문제: icpc.me/1183 도착하는 시간 A 배열과 기다리는 시간 S배열이 주어질 때 SUM[ abs(S[i]-A[i]+T) ] 을 최소로 만드는 T의 개수를 세는 것이다. 어짜피 s배열과 a배열 둘다 입력으로 주어지는 수니 수식의 간편화를 위하여 X로 표시할 수 있다 결국 우리는 SUM[ abs(X[i]+T) ]를 구하면 되는 것이다. X[i]들을 전부 정렬한 후 어떤 수 T를 어떤 수 -X[i]로 잡고 값을 정할 때 T를 -X[i]에서 증가 시킬 경우 (X[i]보다 큰수들-X[i]보다 작은수들)만큼 증가하며 -X[I]에서 감소 시킬 경우 (X[i]보다 작은수들-X[i]보다 큰수들)만큼 증가하게 된다. 결국 이를 이용하여 생각하면 정렬을 했을 때 중앙값의 음수부호를 취해준 -X[i]가 합을 최소로 .. 더보기
BOJ)2022 사다리 문제: icpc.me/2022 극혐스러운 수학문제이다. 사실 그렇게 어려운 수식은 아니고 직선의 방정식 두개를 구하여 두 교점의 y좌표인 c를 알고 있으니 이때 구해야하는 밑면 m을 이분 탐색을 통하여 찾아 나가는 문제이다. 밑면m이 클수록 c는 낮아지므로 함수로 구한 값이 c보다 크다면 lo를 mid로 c보다 작다면 hi를 mid로 잡아주면 된다. 사실 이터레이터를 얼마나 돌려야되는지 감이 안와서 제출하면서 조절했는데 너무 많이 돌리면 TLE를 보게되고 너무 적게 돌리면 오차때문에 WA를 보게된다. 123456789101112131415161718192021222324252627#include #include using namespace std;double x, y, c, lo, hi;double fx.. 더보기
BOJ 7894) 큰 숫자 문제: icpc.me/7894 BOJ 7894 임의의 숫자 n의 자리수는 ceil(log10(n))으로 결정된다 n!의 자리수는 ceil(log10(n)+log10(n-1)+...+log10(1)) 으로 결정된다. 12345678910111213141516171819202122#include #include #include using namespace std;int t, m;int main() { scanf("%d", &t); while (t--) { scanf("%d", &m); double r = 0.0; for (double i = (double)m; i > 0; i--) { r += log10(i); } if (m == 1) printf("1\n"); else printf("%lld\n", (in.. 더보기

티스토리툴바