뺄셈의 경우 먼저 mod를 한 결과가 음수가 나올 수 있기때문에 (A-B)%M = ((A%M)-(B%M)+M)%M을 해줘야한다.
#include <iostream>
using namespace std;
int main(){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
// 첫째 줄에 (A+B)%C, 둘째 줄에 (A%C + B%C)%C, 셋째 줄에 (A×B)%C, 넷째 줄에 (A%C × B%C)%C를 출력한다.
printf("%d\n%d\n%d\n%d",(a+b)%c,(a%c+b%c)%c,(a*b)%c,(a%c*b%c)%c);
}
최대공약수(Gretest Common Divisor)
두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다. 이때 최대공약수가 1인 두 수를 서로소(Coprime)이라고 한다.
2부터 min(A,B)까지 모든 정수로 나누어보는 방법
유클리드 알고리즘(a를 b로 나눈 나머지를 r이라 했을 때, GCD(a,b)=GCD(b,r), r=0이면 그 때 b가 최대공약수이다.)
#include <iostream>
using namespace std;
//2. 유클리드 알고리즘 재귀
int gcd(int a, int b){
if(b==0){
return a;
}else{
return gcd(b,a%b);
}
}
//3. 유클리드 알고리즘 비재귀
int gcd2(int a,int b){
while(b!=0){
int r=a%b;
a=b;
b=r;
}
return a;
}
int main(){
int a,b,g;
scanf("%d %d",&a,&b);
g=1;
//1. 모든 정수
for(int i=2;i<=min(a,b);i++){
if(a%i==0 && b%i==0){
g=i;
}
}
}
a<b인 경우엔느 a%b=a이므로 자동으로 a와 b가 바뀌게 된다. 그러므로 따로 대소관계를 비교해줄 필요가 없다.
세 개이상의 최대공약수는 **GCD(a,b,c)=GCD(GCD(a,b),c)**와 같은 식으로 계속해서 구할 수 있다.
최소공배수(Least Common Multiple)
두 수의 공통된 배수 중에서 가장 작은 정수이다. 최소공배수는 최대공약수를 이용해서 구할 수 있다. 이 때, 최소공배수는 두 수보다 큰 수이므로 범위를 잘 확인해서 구해야한다.
**최대공약수 * 최소공배수 = A*B**이다.
즉, **최소공배수 = (A*B)/최대공약수**이다.
#include <iostream>
using namespace std;
int gcd(int a, int b){
if(b==0)return a;
else{
return gcd(b,a%b);
}
}
int main(){
int a,b,g,l;
scanf("%d %d",&a,&b); //이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
g=gcd(a,b); //최대공약수
l=(a*b)/g; //최소공배수
printf("%d\n%d",g,l);
}
#include <iostream>
using namespace std;
int gcd(int a, int b){
if(b==0)return a;
else{
return gcd(b,a%b);
}
}
int main(){
int a,b,g,l,t;
scanf("%d",&t);
while(t--){
scanf("%d %d",&a,&b); //이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
g=gcd(a,b);
l=(a*b)/g;
printf("%d\n",l);
}
}
//양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.
#include <iostream>
using namespace std;
int gcd(int a, int b){
if(b==0)return a;
else return gcd(b,a%b);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
int num[101]={0};
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&num[i]);
long long int sum=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
sum+=gcd(num[i],num[j]);
}
}
printf("%lld\n",sum);
}
}
진법 변환
10진법 수 N을 B진법으로 바꾸려면 N이 0이 될때까지 나머지를 계속해서 구하면된다.
ex)11을 3진법으로 바꾸는 방법
11/3=3...2
3/3=1...0
1/3=0...1
정답 102
10 to N
10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오.
A: 10, B: 11, ..., F: 16, ..., Y: 34, Z: 35
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
int n,b;
scanf("%d %d",&n, &b);
string ans="";
while(n>0){
int r=n%b;
if(r<10){
ans+=(char)(r+'0');
}else{
ans+=(char)(r-10+'A');
}
n/=b;
}
reverse(ans.begin(),ans.end());
cout << ans;
}
B to 10
B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.
A: 10, B: 11, ..., F: 16, ..., Y: 34, Z: 35
#include <iostream>
#include <string>
using namespace std;
int main(){
int ans=0;
int b;
string s;
cin >> s >> b;
for(int i=0;i<s.size();i++){
if('0'<=s[i]&&s[i]<='9'){
ans=ans*b+s[i]-'0';
}else{
ans=ans*b+s[i]-'A'+10;
}
}
printf("%d",ans);
}
2 to 8
2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오.
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size();
if (n%3 == 1) {
cout << s[0];
} else if (n%3 == 2) {
cout << (s[0]-'0')*2 + (s[1]-'0');
}
for (int i=n%3; i<n; i+=3) {
cout << (s[i]-'0')*4 + (s[i+1]-'0')*2 + (s[i+2]-'0');
}
cout << '\n';
return 0;
}
8 to 2
8진수가 주어졌을 때, 2진수로 변환하는 프로그램을 작성하시오.
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
string eight[8] = {"000","001","010","011","100","101","110","111"};
int main(){
string s;
cin >> s;
bool st = false;
if(s.length() == 1 && s[0]-'0' == 0)cout << "0";
for(int i = 0;i < s.length();i ++){
int n = s[i]-'0';
if(!st && n < 4){
if(n == 0) continue;
else if(n == 1) cout << "1";
else if(n == 2) cout << "10";
else if(n == 3) cout << "11";
st = true;
}
else{
cout << eight[n];
st = true;
}
}
return 0;
}
8 to -2
-2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다.
나머지가 음수가 나오면 안된다.
양수/-2
2로 나누어 떨어지는 경우
음수/-2
2로 나누어 떨어지는 경우
/*
8진수가 주어졌을 때, 2진수로 변환하는 프로그램을 작성하시오.
첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다.
첫째 줄에 주어진 수를 2진수로 변환하여 출력한다. 수가 0인 경우를 제외하고는 반드시 1로 시작해야 한다.
*/
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
int main(){
int n;
scanf("%d",&n);
string ans="";
if(n==0)printf("%d",n);
while(n!=1){
if(n>0){
if(n%(-2)==0){
ans+='0';
}else{
ans+='1';
}
}else{
if(n%(-2)==0){
ans+='0';
}else{
ans+='1';
n-=1;
}
}
n/=-2;
}
ans+='1';
reverse(ans.begin(), ans.end());
cout << ans;
}
A to B
A진법을 B진법으로 바꾸기
A진법 -> 10진법 -> B진법
#include <iostream>
using namespace std;
void convert(int num, int base) {
if (num == 0) return;
convert(num/base, base);
printf("%d ",num%base);
}
int main() {
int a,b;
cin >> a >> b;
int n;
cin >> n;
int ans = 0;
for (int i=0; i<n; i++) {
int x;
cin >> x;
ans = ans * a + x;
}
convert(ans,b);
return 0;
}
1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다. 왜냐하면 각각의 수에 대해서 소수인지 아닌지 검사하는데 O(root(N))시간이 걸리는데, N개를 검사해야하므로 O(Nroot(N))의 시간이 걸리므로 너무 긴 시간이 걸린다.
에라토스테네스의 체는 다음과 같은 규칙으로 구한다.
2부터 N까지 모든 수를 써놓는다.
아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
그 수는 소수이다.
이제 그 수의 배수를 모두 지운다.
이렇게 지우고 남아 있는 수가 모두 소수이다.
구현
int p[100]; //소수 저장할 배열
int total_prime = 0; //소수의 개수
bool c[101]; //지워지면 true, 아니면 false
int n = 100; //N까지의 수
for(int i=2;i<=n;i++){
if(c[i]==false){
p[total_prime++]=i;
for(int j=i*i;j<=n;j+=i)c[j]=true;
}
}
시간복잡도 : O(Nloglog(N))
n/2 + n/3 + n/4 + …. = loglog(N)
주의할 점 i*i는 N의 범위에 따라서 i+i로 변경해준다.(백만이상일 경우 범위 초과)
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
#include <iostream>
using namespace std;
#define MAX 1000000
int p[MAX];
int total_prime=0;
bool check_prime[MAX+1];
int main(int argc, const char * argv[]) {
int n,m;
scanf("%d %d",&m, &n);
for(int i=2;i<=n;i++){
if(check_prime[i]==false){
if(i>=m){
p[total_prime++]=i;
printf("%d\n",i);
}
for(int j=i+i;j<=n;j+=i){
check_prime[j]=true;
}
}
}
}
증명이 되지 않은 문제여서 추측이라고 한다.
2보다 큰 모든 짝수는 두 소수의 합으로 표현이 가능하다.
5보다 큰 모든 홀수는 세 소수의 합으로 표현이 가능하다.
10^18이하에서는 참인 것이 증명되어 있다.
#include <iostream>
using namespace std;
#define MAX 1000000
int p[MAX];
int total_prime=0;
bool check_prime[MAX+1];
int main(int argc, const char * argv[]) {
int t;
for(int i=2;i<=MAX;i++){
if(check_prime[i]==false){
p[total_prime++]=i;
for(int j=i+i;j<=MAX;j+=i){
check_prime[j]=true;
}
}
while(1){
scanf("%d",&t);
if(t==0)break;
for(int i=1;i<total_prime;i++){
if(check_prime[t-p[i]]==false){
printf("%d = %d + %d\n", t, p[i],t-p[i]);
break;
}
}
}
}
하지만 실제로 구할 때 소인수분해를 다 할 필요는 없다. 5의 개수가 항상 2의 개수보다 적기 때문에 5의 개수만 세어주면된다.
N!의 0의 개수 = [N/5]+[N/5^2]+[N/5^3]+…
예를 들어 100!이면 (100/5 = 20) + (100/25) = 24개이다.
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int n;
scanf("%d",&n);
int res = 0;
for (int i=5; i<=n; i*=5) {
res += n/i;
}
printf("%d",res);
}
nCm의 끝자리 0의 개수를 구하는 문제이다. 팩토리얼에서는 2의 개수가 5의 개수보다 항상 많기 때문에 5만 세어줬지만, 조합은 어떻게 될지 모르기 때문에 2와 5의 개수를 모두 세어줘야한다.
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
long long n,m;
scanf("%lld %lld",&n,&m);
long long two=0, fiv=0;
long long i;
for (i=2; i<=n; i*=2) {
two += n/i;
}
for (i=2; i<=n-m; i*=2) {
two -= (n-m)/i;
}
for (i=2; i<=m; i*=2) {
two -= m/i;
}
for (i=5; i<=n; i*=5) {
fiv += n/i;
}
for (i=5; i<=n-m; i*=5) {
fiv -= (n-m)/i;
}
for (i=5; i<=m; i*=5) {
fiv -= m/i;
}
if(fiv>two)printf("%lld",two);
else printf("%d",fiv);
}
