· [블 루 브리지] · 만두 채 우기

제목: · [블 루 브리지] · 만두 채 우기 태그:

수론

블 루 브리지

categories:

제목

제목 출처: 만 두 는 전형 적 인 Ax + By = C 문 제 를 모 으 고 다른 블 로 그 는 Ax + By = C 의 풀이 토론 (A, B 만 상수) 을 상세 하 게 요약 했다.
문 제 는 샤 오 밍 이 거의 매일 아침 만두 가게 에서 아침 을 먹는다 는 것 이다.그 는 이 만두 에 N 종의 시루 가 깔 려 있 는 것 을 발 견 했 는데, 그 중에서 i 종의 시루 는 마침 Ai 의 만 두 를 넣 을 수 있다.모든 시루 에는 매우 많은 시루 가 있어 무한 시루 라 고 볼 수 있다.고객 이 X 개의 만 두 를 사고 싶 어 할 때마다 만 두 를 파 는 아 저 씨 는 몇 개의 만 두 를 신속하게 골 라 서 이 몇 개의 바구니 에 모두 X 개의 만 두 를 가지 게 한다.예 를 들 어 모두 3 가지 시루 가 있 는데 각각 3, 4, 5 개의 만 두 를 넣 을 수 있다.손님 이 만두 11 개 를 사려 고 할 때 아 저 씨 는 2 바구니 3 개 에 1 바구니 5 개 를 더 한다 (1 바구니 3 개 에 2 바구니 4 개 를 더 할 수도 있다).물론 만두 아 저 씨 는 손님 이 사고 싶 은 수량 을 도저히 모 을 수 없 을 때 도 있 습 니 다.예 를 들 어 모두 세 종류의 시루 가 있 는데 각각 4, 5, 6 개의 만 두 를 넣 을 수 있다.손님 이 만두 7 개 를 사려 고 할 때 아 저 씨 는 모 을 수가 없 었 습 니 다.샤 오 밍 은 모두 몇 가지 숫자 가 만두 아저씨 가 모 을 수 없 는 지 알 고 싶 어 한다.입력 형식 첫 줄 에는 정수 N 이 포함 되 어 있 습 니 다.(1 < = N < = 100) 이하 N 줄 마다 하나의 정수 Ai 가 포함 되 어 있 습 니 다.(1 < = Ai < = 100) 출력 형식 은 하나의 정수 가 답 을 나타 낸다.모 을 수 없 는 숫자 가 무한 여 개 라면 INF 를 출력 합 니 다.샘플 입력 245 샘플 출력 6 샘플 입력 246 샘플 출력 INF 샘플 설명 샘플 1 에 대해 모 을 수 없 는 수량 은 1, 2, 3, 6, 7, 11 을 포함한다.샘플 2 에 대해 서 는 모든 기 수 를 모 을 수 없 기 때문에 무한 여러 개가 있다.
제목 분석

다른 블 로그 종 에 따라 Ax + By = C 에 대한 토론 (A, B 만 상수), Ax + By = C 는 \ (a 0x 0 + a 1x 1 +... + a {n - 1} x {n - 1} = c \)

로 보급 할 수 있 습 니 다.

\ \ (a 0, a 1,... a {n - 1} \) 서로 질 이 맞지 않 으 면 풀 리 지 않 는 C 의 개 수 는 INF 이다.

반대로 풀 리 지 않 는 C 의 개수 가 제한 되 어 있 습 니 다. C 는 최대 \ (max \ {C | C 로 인해 풀 리 지 않 습 니 다 \} = a 0 * a 1 *... * a {n - 1} - (a 0 + a 1 +... + a {n - 1}) \ 를 입력 하 십시오. 이 max 는 10000 보다 작 습 니 다.먼저 주 함수 - - - - - - - - - - - - -

int Gcd(int a, int b)
{
	if(!b)
		return a;
	return Gcd(b, a%b);
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
	}
	int g;
	for(int i = 1; i <= n; ++i){
		if(i == 1)
			g = a[i];
		else
			g = Gcd(g, a[i]);
	}
	if(g != 1){//    ，c      INF
		printf("INF
");
		return 0;
	}
	solve();
	return 0;
}

다음은 주로 상호 질 적 조건 에서 C 가 풀 리 지 않 는 개수 알고리즘 사상 을 어떻게 확정 하 는 지 토론 하 는 것 이다. 사실은 완전한 가방 이다. 선택 할 수 있 는 물품 의 개수 가 매우 많 기 때문에 C 를 만 들 수 있 는 지 없 는 지 를 볼 수 있 지만 가방 가치 와 관련 되 지 않 기 때문에 dp 를 설치 할 필요 가 없다.에 식 체 소수 와 유사 한 알고리즘 은 C 의 범위 (0, 10000) 를 확 정 했 고 하나의 배열 num [] 을 정의 했다. 범위 가 가장 크 면 자연히 10000 이다.만약 에 mum [j] 가 C 를 만 들 수 있다 면 num [j + a [i] 는 C 를 만 들 수 있 고 체 를 칠 때 i 와 j 순환 의 선후 에 주의 할 수 있 습 니 다. - - - - - - - - - - - - - - - - - - - -

int n, a[105];
bool num[10000];
void solve()
{
	num[0] = true;
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 0; j < 10000; ++j)
		{
			if(num[j])
				num[j+a[i]] = true;
		}
	}
	int ans = 0;
	for(int i = 0; i < 10000; ++i)
	{
		if(!num[i])
		{
			++ans;
		}
	}
	printf("%d
", ans);
}

- - - - - - 업데이트 에 실 패 했 습 니 다. 나중에 다른 방법 을 생각해 낼 수 있 는 지 확인 하 세 요.