https://www.acmicpc.net/problem/2609
유클리드 호재법 알고리즘이다.
최대공약수 GCD(Greatest Common Divisor)
최소공배수 LCM(Least Common Multiple)
ex) 72 와 30의 최소공배수는 360이다.
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
if (a % b == 0)
return b;
else
return gcd(b, a % b);
}
int main(void)
{
freopen("input.txt", "r", stdin);
int a, b;
scanf("%d %d", &a, &b);
int ans = gcd(a, b);
printf("%d\n%d\n", ans, a*b/ans);
}
https://www.acmicpc.net/problem/1934
동일한 문제이다.
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
if (a % b == 0)
return b;
else
return gcd(b, a % b);
}
int main(void)
{
freopen("input.txt", "r", stdin);
int c;
scanf("%d\n", &c);
while (c--)
{
int a, b;
scanf("%d %d", &a, &b);
int ans = gcd(a, b);
printf("%d\n", a * b / ans);
}
}
https://www.acmicpc.net/problem/1978
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int find_sosu(int d)
{
if (d <= 1) return false;
for (int i = 2; i <= sqrt(d); ++i)
{
if (d % i == 0)
{
return false;
}
}
return true;
}
int main(void)
{
freopen("input.txt", "r", stdin);
int c;
scanf("%d\n", &c);
int ans = 0;
while (c--)
{
int d;
scanf("%d", &d);
ans += find_sosu(d) ? 1 : 0;
}
printf("%d\n", ans);
}
소수를 푸는 가장 쉬운 방법은 루트보다 작을때까지의 값들을 나누어 보는 것이다.
입력이 적다면 쓸 수 있는 간단한 알고리즘이지만 이거 생각보다 속도가 매우 느리다.
그래서 뒤에서 골드바흐의 추측이 나오게 된다. 에라토스테네스의 채라는 풀이 인데 방법이 두 가지가 있었다.
https://www.acmicpc.net/problem/1929
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int find_sosu(int d)
{
if (d <= 1) return false;
for (int i = 2; i <= sqrt(d); ++i)
{
if (d % i == 0)
{
return false;
}
}
return true;
}
int main(void)
{
//freopen("input.txt", "r", stdin);
int a, b;
scanf("%d %d", &a, &b);
for (int i = a; i <= b; ++i)
{
if (find_sosu(i))
printf("%d\n", i);
else
continue;
}
return 0;
}
https://www.acmicpc.net/problem/6588
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int find_sosu(int d)
{
if (d <= 1) return false;
for (int i = 2; i <= sqrt(d); ++i)
{
if (d % i == 0)
{
return false;
}
}
return true;
}
int main(void)
{
freopen("input.txt", "r", stdin);
int d = 0;
char map[1000001] = { 0 };
for (int i = 2; i * i <= 1000000; i++)
{
if (map[i] == 0)
{
for (int j = i + i; j <= 1000000; j += i)
{
map[j] = 1;
}
}
}
vector<int> prime;
for (int i = 2; i <= 1000000; i++)
{
if(map[i] == 0)
prime.push_back(i);
}
while (scanf("%d", &d))
{
if (d == 0) break;
for (int i = 0; prime[i] < d; i++)
{
int b = d - prime[i];
if (find_sosu(b))
{
printf("%d = %d + %d\n", d, prime[i], b);
break;
}
}
}
return 0;
}
위와같이 시작 2부터해서 그거의 배수를 미리 배열에 저장해 놓으면 소수만 남게 된다는 원리인데
이게 메모리를 많이 차지해서 나도 에러를 몇 번 먹고 map을 char로 선언하게 되었다;;
사실 아래 짓거리 해도 문제가 풀리기는 한다;;
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int find_sosu(int d)
{
if (d <= 1) return false;
for (int i = 2; i <= sqrt(d); ++i)
{
if (d % i == 0)
{
return false;
}
}
return true;
}
int main(void)
{
//freopen("input.txt", "r", stdin);
int d = 0;
while (scanf("%d", &d))
{
if (d == 0) break;
for (int i = 1; i < d / 2; i++)
{
int a = i * 2 + 1;
int b = d - a;
if (find_sosu(a) && find_sosu(b))
{
printf("%d = %d + %d\n", d, a, b);
break;
}
}
}
return 0;
}
그냥 소수는 2를 제외하고 홀수이기 때문에 그거의 배수로 계산을 때려버리면 결과가 빠르게 나온다.
심지어 속도 차이도 난다;;
https://www.acmicpc.net/problem/10872
팩토리얼 계열의 문제이다.
그냥 점화식으로 풀면된다.
맞다. 수학에서부터 점화식이 나온다.
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int facto(int n)
{
if (n <= 1) return 1;
return n * facto(n - 1);
}
int main(void)
{
//freopen("input.txt", "r", stdin);
int d = 0;
scanf("%d\n", &d);
printf("%d\n", facto(d));
}
https://www.acmicpc.net/problem/1676
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main(void)
{
//freopen("input.txt", "r", stdin);
int d = 0;
scanf("%d\n", &d);
int ans = 0;
for (int i = 5; i <= d; i *= 5)
{
ans += d / i;
}
printf("%d\n", ans);
return 0;
}
이건 팩토리얼과 1도 관계가 없어보일 수도 있지만
팩토리얼의 특성을 가지고 푸는 문제이다.
https://torbjorn.tistory.com/247
대충 100! 을 구한다고 하더라도 5로 나누면 5와 관련된 숫자가 나오는 경우는 20회 정도이다.
25로 나누면 4회
그래서 100! 에서 0이 나오는 경우는 24회인데
실재로도 24회이다.
그래서 5의 제곱승으로 나누어주면된다. 이건 트릭치한것이기 때문에 이렇게 풀 수 있다고 인지하자
https://www.acmicpc.net/problem/2004
사실 이것도 비슷한데 nCr을 해주면 n!/(r! * (n-r)!) 으로 계산하게 된다.
그래서
n!
r!
(n-r)!
에서 5의 제곱수들로 나눈 것을 모두 합하면 답이 나온다.
여기서 주의점은 입력값이 int를 넘어가기 때문에 자료형 선정에 주의를 요한다는 점과
2와 5로 나눈 것 중 어느 것이 더 적은 수인지 모르기 때문에 두 가지를 모두 비교해주어야 한다는 점이다.
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int div_n(long long n, int div)
{
int ans = 0;
for (long long i = div; i <= n; i *= div)
{
ans += n / i;
}
return ans;
}
int main(void)
{
//freopen("input.txt", "r", stdin);
long long a,b = 0;
scanf("%lld %lld\n", &a,&b);
long long div_five = div_n(a,5) - div_n(b,5) - div_n(a - b,5);
long long div_two = div_n(a, 2) - div_n(b, 2) - div_n(a - b, 2);
printf("%d\n", min(div_five,div_two));
return 0;
}
https://www.acmicpc.net/problem/9613
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int gcd(int a, int b)
{
if (a % b == 0) return b;
return gcd(b, a % b);
}
int main(void)
{
//freopen("input.txt", "r", stdin);
int t = 0;
scanf("%d\n", &t);
while (t--)
{
int c = 0;
scanf("%d", &c);
vector<int> d;
for (int i = 0; i < c; ++i)
{
int tmp = 0;
scanf("%d", &tmp);
d.push_back(tmp);
}
long long ans = 0;
for (int i = 0; i < c; ++i)
{
for (int j = i + 1; j < c; ++j)
{
ans += gcd(d[i], d[j]);
}
}
printf("%lld\n", ans);
}
return 0;
}
그냥 기존에 연습한거 잘 활용해주면 된다.
https://www.acmicpc.net/problem/17087
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
long long gcd(long long a, long long b)
{
if (a % b == 0) return b;
return gcd(b, a % b);
}
int main(void)
{
//freopen("input.txt", "r", stdin);
long long n, s;
scanf("%lld %lld\n", &n, &s);
vector<long long> d;
long long cnt = n;
while (cnt--)
{
long long tmp;
scanf("%lld", &tmp);
d.push_back(abs(s-tmp));
}
long long ans = d[0];
for (int i = 1; i < n; ++i)
{
ans = gcd(ans, d[i]);
}
printf("%d\n", ans);
return 0;
}
이것도 비슷하게 gcd를 잘 응용해주라는 문제이다.
https://www.acmicpc.net/problem/1373
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main(void)
{
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string d;
cin >> d;
while (d.length() % 3 != 0)
{
d = '0' + d;
}
for (int i = 0; i < d.length(); i += 3)
{
int ans = (d[i] - '0') * 4 + (d[i + 1] - '0') * 2 + (d[i + 2] - '0') * 1;
cout << ans;
}
return 0;
}
진법변환문제인데 여기에서부터 주의할 점은 string을 사용할 경우 scanf를 사용 못한다. 그래서 cin을 써야하는데 cin을 쓴다면 ios_base와 cin.tie, cout.tie 문법을 써줄 수 있어서 속도를 조금 더 높히었다.
알고리즘은 단순하게 3자리수씩 끊어서 생각하면된다.
https://nanyoungkim.tistory.com/174
이 분 블로그를 참고하였다.
https://www.acmicpc.net/problem/1212
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
int main(void)
{
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string d;
cin >> d;
string eight[8] = { "000","001","010","011","100","101","110","111" };
for (int i = 0; i < d.length(); ++i)
{
int tmp = d[i] - '0';
if (i == 0) cout << stoi(eight[tmp]);
else cout << eight[tmp];
}
}
https://velog.io/@ap3334/%EB%B0%B1%EC%A4%80-C-1212.-8%EC%A7%84%EC%88%98-2%EC%A7%84%EC%88%98
https://velog.io/@youhyeoneee/%EB%B0%B1%EC%A4%80-2089%EB%B2%88-2%EC%A7%84%EC%88%98
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int N;
void trans(int n){
if (n == 0)
return;
// 경우 1. 2로 나눠지는 경우
if (n % 2 == 0){
trans(-(n/2));
cout << 0;
}
else{
// 경우 2-1. 2로 나눠지지 않는 경우 + 양수 인 경우
if(n > 0)
trans(-(n / 2));
// 경우 2-2. 2로 나눠지지 않는 경우 + 음수 인 경우
else
trans((-n + 1) / 2);
cout << 1;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
if (N == 0)
cout << 0;
else
trans(N);
cout << '\n';
return 0;
}