0과 1의 쉼터

소스코드 #include #include #define MAX 1001 bool not_prime[MAX]; int main(){ int N, K; scanf("%d %d", &N, &K); for (int i = 2; i

풀이 연속된 소수의 합이므로, 소수로만 이루어진 배열에서 투 포인트를 적용하면 된다. 에라토스테네스의 체로 소수가 아닌 것들을 구분하여 소수로만 이루어진 배열을 만들고, 투 포인트 방식으로 풀이했다. 소스코드 #include #include #include #define MAX 4000001 bool not_prime[MAX]; int sum_prime[MAX/10]; int main(){ int N; scanf("%d", &N); int sq = sqrt(N); for (int i = 2; i

풀이 위의 예제는 다음과 같은 규칙이 있다. gcd(1, 소수) = 1 이므로 계산할 필요가 없으며, gcd(소수, 소수) = 소수 이다. gcd(N, M) = K일 때, gcd(N + K*i, M + K*i)는 모두 K이다. (단, i = 2~N or M) 위의 조건에서 얻은 K는 K의 제곱수가 존재할 경우 변경된다. N과 M크기를 이용해 K의 개수를 구할 수 있다. 두번째 조건에서 얻은 K들의 곱들과 세번째 조건에서 얻은 수의 중복을 피해야 한다. 다음과 같이 p+K*i (단, i = 0 ~ (p+K*i

풀이 "백준 11689, GCD(n, k) = 1"를 이용해 풀이했다. 시간초과는 발생하지 않으니 그냥 0을 입력받을 때까지 반복하면된다. 소스코드 #include int main(){ long long n; while (1){ scanf("%lld", &n); if (!n) break; long long euler = n; for (long long p = 2; p*p

풀이 Euclidean algorithm을 사용해 풀이할 수 있지만, 최대 10^12의 수들에 대해 계산을 해야하므로 시간제한에 걸린다. Euler product formula을 사용해 쉽게 풀이할 수 있다. 나누어 떨어지는 소인수(p)를 찾아 Euler product formula에 적용시키면 된다. p-1 / p (= 1- 1/p)를 n에 곱해주어야 한다. p로 먼저 나눈 후 p-1을 곱해주자. for (long long p = 2; p*p

풀이 마지막 예제에서 힌트를 얻었다. 입력된 두 정수의 최대공약수 만큼 1을 출력해주면 된다. 소스코드 #include #define LL long long LL GCD(LL a, LL b){ return b ? GCD(b, a%b) : a; } int main(){ LL A, B; scanf("%lld %lld", &A, &B); LL i = GCD(A, B); while (i--) putchar('1'); } 출처 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net

풀이 입력받은 두 분수를 통분하고, 분자와 분모의 최대공약수를 이용해 약분하여 분수형태로 출력하면 된다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int A, B, a, b; scanf("%d %d %d %d", &A, &B, &a, &b); int AA = A*b + a*B, BB = B*b; int gcd = GCD(AA, BB); printf("%d %d\n", AA/gcd, BB/gcd); } 출처 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net

풀이 처음에 입력받은 링의 반지름과 이후에 입력받은 반지름의 최대공약수를 이용해 약분하여 분수형태로 출력하면 된다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int N, first_r, r; scanf("%d %d", &N, &first_r); while (-1 + N--){ scanf("%d", &r); int gcd = GCD(first_r, r); printf("%d/%d\n", first_r/gcd, r/gcd); } } 출처 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 ..

풀이 모든 쌍의 GCD를 구해서 합해주면 된다. 단, 최악의 경우 1,000,000 * 99 * 98 * 97 *... * 3 * 2 *1 의 수가 나올 수 있으니 long long 자료형의 변수에 합을 담아주어야 한다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int t, n, arr[100]; scanf("%d", &t); while (t--){ scanf("%d", &n); long long gcd_sum = 0; for (int i = 0; i < n; i++) scanf("%d", &arr[i]); for (int i = 0; i < n-1; i++) for (int j = 1 + i; j < n..

풀이 두 수의 곱을 최대공약수로 나누면 최소공배수이다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int T, A, B; scanf("%d", &T); while (T--){ scanf("%d %d", &A, &B); printf("%d\n", A*B / GCD(A, B)); } } 출처 및 참고자료 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net [백준 2609] 최대공약수와 최소공배수 [C..