정수론과 조합론

유클리드 호제법

 : 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a > b), a와 b의 최대 공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다. 

 

1. a % b = r

2. gcd(a, b) = gcd (b, r)

 

static long gcd(long a, long b) {
  while(b != 0) {
    long r = a % b;
    a = b;
    b = r;
  }
  return Math.abs(a);
}

 

 

 

 

 

확장 유클리드 호제법

: 특정 방정식을 만족하는 해를 구할 수 있다. 

 

public class P3955 {
  static int T;
  static long A, B;

  public static void main(String[] args) {
    // X : 인당 나눠줄 사탕의 수
    // Y : 사탕 봉지의 수
    // A * X + 1 = B * Y   =>    A(-x) + By = 1 
    Scanner sc = new Scanner(System.in);
    T = sc.nextInt();

    for(int t=0; t < T ; t++) {
      //A, B 입력
      A = sc.nextLong();
      B = sc.nextLong();

      //D = gcd(A, B)
      //D * k = C ==> C % D == 0 : 베주 항등식
      //확장 유클리드 호제법을 이용하여 s, t, r = D을 찾아냄.
      long [] str = eGcd(A, B);
      long D = str[2];

      //			System.out.println(Arrays.toString(str));
      if(1 % D != 0) {
        System.out.println("IMPOSSIBLE");
        continue;
      }
      // x0 = s * (C/D)
      // y0 = t * (C/D)
      long x0 = str[0];		//C =1, D = 1
      long y0 = str[1];
      //			System.out.println(x0+", "+ y0);
      //일반 해 공식 (k 는 일반해에서 나오는 k)
      // x = x0 + B/D * k
      // y = y0 - A/D * k

      // x < 0 -> 방정식의 형태를 맞춰주기위해 부호를 바꾸었기 때문에 
      // x0 + B/D*k < 0
      // k < - x0 / B * D

      // 0 < y <= 10^9 (1e9)
      // 0 < y0 - A/D*k <= 1e9
      // -y0 < - A/D * k <= 1e9 - y0

      // (D/A) * (y0 - 1e9) <= k < y0 * (D/A)
      // 						k < - x0 / B*D
      long k1 = (long)Math.ceil((double)-x0 * D / B)-1;
      long k2 = (long)Math.ceil((double)y0 * D / A)-1;
      //			System.out.println(k1+", "+k2);
      // k1과 k2가 범위의 최대 값이므로 둘을 만족하려면 min으로 k의 max값을 구해내야 한다.
      // k의 max를 구한 후 그 k를 이용해서 y값을 구해냅니다. => k가 커지면 y가 작아지므로

      long k = (long)Math.min(k1, k2);
      long y = y0 - A/D * k;
      if (y <= 1e9) {
        System.out.println(y);
      }
      else
      System.out.println("IMPOSSIBLE");
      // 그렇게 구한 y는 가장 작은 y값이다.
      // 그 y값이 1e9 보다 작거나 같으면 가능한 답.
      // 아니면 불가능한 답.
    }

    sc.close();
  }

// ax + by = c => as + bt = r을 만족하는 s, t, r 조합을 찾기 (r이 gcd(a,b)일때)
  static long[] eGcd(long a, long b) {
    long s0 = 1, t0 = 0, r0 = a;
    long s1 = 0, t1 = 1, r1 = b;

    long temp;
    while(r1 != 0) {
      long q = r0 / r1;

      temp = r0 - q * r1; // => 새로운 r 값
      r0 = r1;
      r1 = temp;

      temp = s0 - q * s1;
      s0 = s1;
      s1 = temp;

      temp = t0 - q * t1;
      t0 = t1;
      t1 = temp;
    }

  	return new long[] {s0, t0, r0};
  }
}

에라토스테네스의 체

: 1보다 큰 정수의 양의 약수가 1과 자기자신뿐일때, 그 수를 소수라고 하며 소수를 계산하는 대표적인 방법이다.

 

정수론 백준문제
- 분수 합 (1735)
- 최대공약수 하나 빼기 (14476)
- 캔디 분배 (3955)
- 에라토스테네스의 체 (2960)
- 골드바흐의 추측 (6588)
- 소수의 연속합 (1644)
- 소인수분해 (11653)
- 암호제작 (1837)
- 최대공약수 (2824)
- 보이는 점의 개수 (2725)
- 1 (4375)
- 30 (10610)
- 수학은 너무 쉬워 (2904)
- 소수를 분수로 (5376)

 

조합론 백준문제
- 이항 계수1 (11050)
- 이항 계수2 (11051)
- 다리 놓기 (1010)
- 사전 (1256)
- 카드 놓기 (5568)
- 1학년 (5557)
- 산책 (5573)
- 출근 경로 (5569)
- 순열의 순서 (1722)
- 조약돌 꺼내기 (13251)
- N과 M (9) (15663)
- N과 M (10) (15664)