acmi 님의 블로그

https://www.acmicpc.net/problem/13428알고리즘: fft 풀이(대문자와 소문자가 의미하는 바가 다르다):배열 a[i]와 b[i]를 각각 배열 A와 배열 B에서 i(0두 배열 a, b에 대해 합성곱에서 두 수의 곱셈을 두 수 중 크지 않은 것(c++에서 min함수)으로 바꾼 식을 계산하면 풀 수 있다(단, 배열 a, b의 크기 n은 200000이상으로 하고 100000부터는 a[i]와 b[i]는 0으로 하자). $ c[j]=\sum_{i=0}^{n-1}min(a[i],b[j-i])$ 나이브하게 계산하면 시간 복잡도는 $O(n^{2})$가 되고 시간초과가 난다. i와 j가 0 or 1일때 min(i,j)=i*j임을 이용하자.  f(x)를 x가 양수면 1, 그렇지 않으면 0으로 정의..

유클리드 호제법으로 gcd를 구하는 방법은 다음과 같다:두 자연수 a>b에 대하여 gcd(a,b)=gcd(b,a%b)임을 이용해 두 수 중 큰 것을 작은 것으로 나눠 그 나머지로 대체한다. 이 때 두 수 중 하나가 0이 되면 남은수가 gcd이다. 코드로 구현하면 다음과 같다:int gcd(int a,int b){//a>0, b>0if(b==0)return a;return gcd(b,a%b);}b>a%b이므로 다시 호출되었을 때는 a>b를 만족한다. 그러므로 b가 0인지만 확인하면 된다.a>b를 만족하지 않고 a>0, b>0이기만 해도 된다. 왜냐하면 a이면 gcd(b,a)가 다시 호출되기 때문이다. c언어에서는 a가 음수일 떄 a%b를 음수 또는 0으로 계산하므로 a>0, b>0이도록 해야한다. 양수로 ..