알고리즘 훈련 원숭이 사과 나 누 기

1790 단어 알고리즘C 언어
문제 설명
가을 이 되자 n 마리 의 원숭이 가 사 과 를 한 무더기 따 서 동굴 에 넣 고 다음날 똑 같이 나 누 기로 약속 했다.이 원숭이 들 은 원숭이 왕 손오공 을 매우 숭배 하기 때문에 모두 그 에 게 사 과 를 좀 남 겨 주 고 싶 어한 다.첫 번 째 원숭이 는 몰래 동굴 로 와 서 사 과 를 평균 n 개 로 나 누 어 남 은 m 개의 사 과 를 먹고 한 개 를 숨 겼 다가 남 은 사 과 를 다시 합 쳤 다.이 원숭이 들 은 차례대로 동굴 로 몰래 와 서 똑 같은 조작 을 하 는데 마침 매번 사과 m 개가 남 았 다.다음날 이 원숭이 들 은 동굴 에 와 서 남 은 사 과 를 n 으로 나 누 었 는데 공교롭게도 m 개가 남 았 다.원래 이 원숭이 들 은 적어도 몇 개의 사 과 를 땄 느 냐 고 물 었 다.
입력 형식
두 개의 정수, n m
출력 형식
하나의 정수 는 원래 사과 의 수 를 나타 낸다.
샘플 입력
5 1
샘플 출력
15621
데이터 규모 와 약정
  0이정 도 교수 의 원숭이 분 도 산수 문제 와 비슷 한 이 문 제 는 교묘 하 게 풀 수 있 는 방법 으로 과연 효율 적 이 고 미묘 하 다.
사과 총 수 를 x 로 설정 할 수 있 고 전체 수량 에 (n - 1) * m 개의 사과 로 y = x + (n - 1) * m 를 추가 할 수 있 습 니 다.첫 번 째 원숭이 는 m 개의 사 과 를 먹고 (x - m) * (1 / n) 개 를 숨 겼 다. 즉, 첫 번 째 원숭이 는 모두 y * (1 / n) 개의 사 과 를 가 져 갔 고 사 과 는 남 았 다 (n - 1) / n * y 를 남 겼 다.(스스로 머리 를 써 서 먹고 입 는 것 이 풍족 하 다.) 원숭이 한 마 리 를 추가 했다 고 가정 할 수 있다.
공식: x =  (n ^ n+1) - ((n - 1) * m)
#include <stdio.h>

int main()
{
	int n,m, p, t, sum;
	
	scanf("%d%d", &n, &m);
	
	t = n+1;
	p = 1;
	while(t -- > 0){
		p *= n;
	}
	
	sum   = p - ((n - 1 ) * m);
	
	printf("%d", sum);
	
	return 0;
	
}

그러나 OJ 의 첫 번 째 테스트 데이터 가 잘못 되 어 다음 날 원숭이 들 이 사 과 를 n 부 로 나 눌 때 1 부 는 적어도 1 개 이기 때문에 이 문 제 는 100% 정확 하지 않다.
정정 후 공식 은 x = k (n ^ n + 1) - (n - 1) * m) 
정정 후 해제
#include <stdio.h>

int main()
{
	int n,m, o, p, k, t, sum;
	
	scanf("%d%d", &n, &m);
	
	t = n+1;
	p = 1;
	o = 1;
	k = 1;
	while(t -- > 0){
		p *= n;
		o *= (n-1);
	}
	
	o /= (n-1);
	while(o < m+1){
		k ++;
		p *= k;
		o *= k;
	}
	sum   = p - ((n - 1 ) * m);
	
	printf("%d", sum);
	
	return 0;
	
}

좋은 웹페이지 즐겨찾기