[블 루 브리지 컵] [2013 년 제4 회 진짜 문제] 살 수 없 는 숫자.

제목 설명
샤 오 밍 은 사탕 가 게 를 열 었 다.그 는 과일 사탕 을 한 봉지 에 4 개, 한 봉지 에 7 개 두 가지 로 쌌 다.사탕 은 뜯 어서 팔 수 없다.어린이 가 사탕 을 사 러 왔 을 때, 그 는 이 두 가지 포장 으로 조합 했다.물론 어떤 사탕 의 수 는 조합 할 수 없다. 예 를 들 어 설탕 10 개 를 사 야 한다.컴퓨터 로 테스트 해 보 세 요. 이런 포장 상황 에서 최대 살 수 없 는 수량 은 17 입 니 다.17 이상 의 모든 숫자 는 4 와 7 로 조합 할 수 있다.이 문제 의 요 구 는 두 개의 포장 수량 을 이미 알 고 있 을 때 조합 할 수 없 는 최대 숫자 를 구 하 는 것 이다.
두 개의 정 수 를 입력 하면 각 포장 에 있 는 설탕의 개 수 를 나타 낸다 (모두 1000 보다 많 지 않다).
최대 살 수 없 는 당 수 를 나타 내 는 정수 하 나 를 출력 하 다.
샘플 입력
출력
문 제 를 읽 은 후에 이해 하기 어렵 지 않 습 니 다. 문 제 는 x = a * num 1 + b * num 2, x 가 만족 할 수 없 는 최대 수 입 니 다.
여기에 두 가지 해법 이 적 혀 있다. 1)
초고 지 에서 연산 을 한 결과 전달 공식 과 유사 하 게 하나의 규칙 을 발견 했다. 예 를 들 어 4 7 x 를 입력 하여 20 int temp = 21 / 7; /temp = 3 에서 21 = 37 + 04 (만족) 22 = 27 + 24 23 = 17 + 44 24 = 07 + 64 25 = 37 + 14... temp = 28 / 7; /temp = 4; 28 = 47 + 04； 29.................................................................................

import java.util.Scanner;

public class Main { 
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in
		);
		while (scanner.hasNext()) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			int result=0;
			int c = 0;
			if(a>b){            //     a>b,      ， b    
			    int temp =a;
			    a=b;
			    b=temp;
			}
			for(int i=1;i<a*b;i++){
			   int temp =i/b;    
			   //             4 7   i=50 temp=50/7  temp=7               
			   boolean flag=true;  //                
			   for(int j=temp;j>=0;j--){
			       if((i-j*b)%a!=0){
			           c=i;
			       }else{  
			           flag=false; 
			           break;
			       }
			   }
			  if(flag){
			      result=c;
			  }
			}
			
			System.out.println(result);
		}
	}
}

2) 인터넷 에서 다른 사람의 해법 전재https://blog.csdn.net/qq_34594236/article/details/51484249

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		System.out.println(a*b-a-b);
	}
}

이렇게 바로 AC 가 됩 니 다.
나 와 나의 동료 들 은 모두 놀 라 멍 해 졌 다.
자연수 a, b 상호 질 은 x + by (x, y 는 비 마이너스 정수) 의 최대 정 수 는 ab - a - b 라 고 표시 할 수 없다.
증명:
a 또는 b 가 1 인 경우 증명 하기 쉽 습 니 다. 아래 의 상황 은 모두 a > 1 및 b > 1 의 경우 입 니 다. 먼저 ab - a - b 가 ax + by 로 ab - a - b = ax + by 를 가설 할 수 없다 는 것 을 증명 합 니 다. 그러면 ab = am + bn (m, n 은 모두 1 보다 크 고 왼쪽 am 은 a 의 배수 입 니 다. 그러면 bn 도 a 의 배수 b 가 a 의 배수 가 아니라면 n 이 a 의 배수 만 요구 할 수 있 습 니 다. 그러면...bn = bn 'a > = ba 는 am = ab - bn 이 므 로 am1 의 모순 이다. 이 어 ab - a - b + i 가 x + by (i > 0) 로 표시 할 수 있 음 을 증명 한다. ab 의 상호 질 때문에 최대 공약수 가 1 이다. 전전 상감 의 방법 에 따라 ma + nb = 1 을 알 고 있다. m > 0, n1 (m = 0 은 nb = 1 을 의미 하기 때문에 ab - a - b + i (ma + nb) = (im - 1) a + (a + in - 1) b im - 1 > 0 을 가정 해도 무방 하 다.그럼 ima = i + | in | b > jab, 그래서 im > jb 그래서 ima + inb = (im - jb) a - (| in | - ja) b = i, | in | > ja 를 설명 할 때, 우 리 는 im 을 조정 할 수 있 습 니 다 | in |
문제 에 서 는 두 숫자 가 상호 질 이 라 고 설명 하지 않 았 고 2 와 4 라면 절 차 를 통 해 나 온 결 과 는 2 임 이 분명 하 다.
이 결 과 는 분명히 틀 렸 다.하지만 분명히 oj 는 이런 수 를 설정 하지 않 았 다.
-----------------------------------------
수 개 월 만 에 돌아 와 서 이 문제 의 구 해 를 계속 보충 하 다.
제목 중 a 개 b 를 드 리 겠 습 니 다.
1. 나 는 모두 가 알 고 있 는 척 했다. 베 이 조 등식: x + by = gcd (a, b).증명 약.우 리 는 이 특 해 를 구 한 후에 x + by = c 의 통 해 를 구 할 수 있다.
2. 여기 서 문제 가 요구 하 는 것 은 마이너스 정수 가 있 을 때 (x, y 중 마이너스) c 가 가장 큰 것 은 얼마 입 니까?
3. x + by = c 가 풀 려 면 gcd (a, b) | c (c% gcd (a, b) = 0) 가 있어 야 이 방정식 이 풀 린 다.분명 한 것 은 gcd (a, b) 가 1 이 아 닐 때 방정식 이 풀 리 지 않 는 상황 은 무한 여러 개 이기 때문에 최대 조합 할 수 없 는 수 는 존재 하지 않 는 다.
4. 우 리 는 항상 x 와 y 의 특 해 를 구 할 수 있다. 즉, 베 조 등식 구 해 후의 x 와 y 이지 만 x 와 y 의 해 는 음수 해 일 수 있다.
5. 분명히 여기 x 와 y 는 마이너스 가 될 수 없 기 때문에 이 문제 의 문 제 는 풀 수 있다.최대 조합 할 수 없 는 수 를 구하 다.
6. 여기 또 하나의 정리 가 있 습 니 다. gcd (a, b) = 1 시 (a 와 b 의 상호 질), c > ab - a - b 시 방정식 x + by = c 는 비 마이너스 가 있 습 니 다.그래서 가장 조합 할 수 없 는 숫자 는 ab - a - b 입 니 다.여기 서 모두 가 이 정 리 를 안다 고 가정 하면 당연히 모 르 더 라 도 상관없다. 적어도 지금 은 네가 알 았 으 니 스스로 증명 해 보고 위의 증명 과정 을 참고 할 수 있다.