NYOJ 212 K 꼬리 등수

제목 분석:
이 문 제 는 M * N% R = (M% R) * (N% R)% R 을 이용 해 계산 하 는 것 이다.즉, K 가 먼저% 1000 을 한 다음 에 1001 개의 K% 1000 을 곱 한 것 입 니 다. 이 는 K 나 Power 가 비교적 클 때 이들 이 곱 하면 데이터 가 넘 칠 수 있 기 때 문 입 니 다. 그러면 제 다른 글 에서 대수 에 대해 모델 링 연산 을 하 는 관련 알고리즘 을 참고 해 야 합 니 다.

 1 #include<stdio.h>

 2 #include<stdlib.h>

 3 #include<string.h>  //  memset   

 4 

 5 int Record[1000];//         

 6 

 7 int KTail(int K)

 8 {

 9     memset(Record,0,sizeof(Record));   //         

10     

11     int Product=1;    //        ，     0？  K^0=1<1000，        1000   

12     

13     bool bTakeRecord=false;    //      ，      >=1000

14     

15     if(K>=1000)

16     {

17         bTakeRecord=true;

18         

19         K=K%1000;   //             (M*N)%R = (M%R *N%R)%R

20         

21     

22     }            //                      

23     

24     for(int power=1;power<=1001;power++)    //power 1 1001 

25     {

26         Product*=K;   // Product = (K^Power-1)%1000 * K 

27         

28         if(bTakeRecord||Product>=1000)  //           K^Power>=1000

29         {

30             bTakeRecord=true;  //          false，   

31             

32             Product=Product%1000;  //      3  ！！！ 

33             

34             if(Record[Product]==0)    //           ，          

35             

36                 Record[Product]=power;   //   

37             else

38                 return power+Record[Product];   //   ！   ，         

39                 

40         }

41     }

42     return -1;    //         ，        ，               

43                       

44                  //   ，     

45 }

46 //   

47 int main()

48 {

49     int T,K;

50     scanf("%d",&T);

51     while(T--)

52     {

53         scanf("%d",&K);

54         printf("%d
",KTail(K));

55     }

56     system("pause");

57     return 0;

58 }

문제 풀이:
어떤 문 제 를 받 든 문 제 를 읽 는 것 이 첫 번 째 로 해 야 할 일이 다.그 다음 에 문제 중의 관건 적 인 단어 와 중점 내용 을 분석한다.
위의 문제 에 있어 서 우 리 는 아래 의 요점 을 주의해 야 한다.
1. 네 가지 포 인 트 량: K, M, N, 1000, 그리고 K, M, N 은 자연수
2. K 는 M, N 의 밑 수, M, N 은 K 의 멱 이다.
3. K ^ M 과 K ^ N 모두 1000 이상 이 어야 합 니 다.
4. K ^ M 은 K ^ N 말미 세 자리 와 같다.
5. 출력 할 값 은 M + N 입 니 다.
6. M > N (두 개의 숫자 가 같 지 않 습 니 다.................................................................
분석:
1. 위의 요점 중 1, 2, 3, 5, 6 은 모두 보조 조건 이 고 관건 은 네 번 째 점 을 파악 하 는 것 이다.마지막 세 분 이 같다 는 게 무슨 뜻 이에 요?예 를 들 어 123456 말미 에 세 분 은 '456' 이 고 45678 말미 에 세 분 은 '678' 이다.분명 하 다.분명히 (=. =!) 이 숫자 를 1000 에 맞 추 면 된다.
2. 곰 곰 이 생각해 보면 1000 모델 에 대한 모든 수 는 1000 가지 가능성 (0 ~ 999) 밖 에 없다 는 것 을 알 수 있 습 니 다. 그래서 우 리 는 K ^ Power 중의 Power 를 1 (왜 0 이 아 닙 니까? K ^ 0 = 1 < 1000 이기 때문에 우 리 는 1000 보다 작은 상황 을 고려 하지 않 고 문제 풀이 3 시) 에서 1001 까지 하나씩 값 을 구하 고 똑 같은 두 개의 숫자 가 있 습 니 다.결 과 는 1000 가지 만 가능 하지만 1001 번 의 수치 가 있 기 때문에 1000 번 의 결과 가 달라 도 마지막 의 수 치 는 반드시 앞의 1000 가지 중 하나 와 같 을 것 이다 (관련 지식: 서랍 원리 1).
흐름:
위의 이해 와 분석 에 따 르 면 해결 절 차 는 대체적으로 다음 과 같다.
1. K 크기 획득
2. K ^ Power (Power = 1, 2, 3...............................................................
3. 기록 할 때 이전에 이 값 이 이미 나 타 났 다 는 것 을 발견 하면, 지난번 에 이 값 을 기록 할 때의 Power 값 과 이번 기록 을 시도 할 때의 Power 값 은 각각 N 과 M 이다.
4. 출력 M + N
 
데이터 구조 와 디자인 기법:
1. 사실 이 프로그램 은 데이터 구 조 를 필요 로 하지 않 지만 한 가지 기술 은 언급 해 야 합 니 다. K ^ Power 끝의 세 자리 숫자 는 0 ~ 999 중의 하나 일 수 있 습 니 다. 우 리 는 어떤 결과 가 나 왔 는 지 어떻게 기록 합 니까?가장 좋 은 방법 은 1 차원 배열 을 사용 하 는 것 이다. 비 수 는 딱 1000 이 고 각각 0 ~ 999 개의 상황 이 발생 할 때 Power 의 값 을 기록 하 는 것 이다.액세스 할 때 마지막 세 자릿수 자체 의 값 을 이 배열 의 색인 으로 사용 할 수 있 습 니 다 (관련 지식: 중복 계수 2)
2. 사실 우리 도 K ^ Power 의 값 을 하나씩 구 할 필요 가 없다. 그런 연산 효율 은 너무 낮다.K ^ Power = K ^ (Power - 1) 를 고려 하여 이 성질 을 이용 하여 K ^ 1 의 값 을 구하 고 이에 따라 K ^ 2 에서 K ^ 1001 의 결 과 를 내 놓 으 면 됩 니 다.
   3. K 나 Power 가 비교적 클 때 이들 의 상승 으로 인해 데이터 가 넘 칠 수 있 습 니 다. 그러면 제 다른 글 에서 대수 에 대해 모델 링 연산 을 하 는 알고리즘 을 참고 해 야 합 니 다. 한 마디 로 결 과 는 M * N% R 을 구 하 는 것 입 니 다. M * N 이 넘 칠 수 있 을 때 (M% R) * (N% R)% R 을 사용 하여 계산 해 야 합 니 다.
관련 지식:
1. 서랍 의 원리:
책상 위 에 사과 가 열 개 있 습 니 다. 이 열 개의 사 과 를 9 개의 서랍 에 넣 어야 합 니 다. 아무리 넣 어도 어떤 서랍 은 하 나 를 넣 을 수 있 고, 어떤 서랍 은 두 개 를 넣 을 수 있 으 며, 어떤 것 은 다섯 개 를 넣 을 수 있 습 니 다. 그러나 결국 우 리 는 적어도 한 서랍 안에 적어도 두 개의 사 과 를 넣 을 수 있다 는 것 을 알 게 될 것 입 니 다.이 현상 은 바로 우리 가 말 한 서랍 원리 이다.
 
2. 반복 계수:
이런 필기시험 문 제 를 만난 적 이 있 습 니 다. 파일 에서 데 이 터 를 읽 으 면 줄 마다 독립 된 숫자 N (N > = 0 및 N < = 65535) 이 고 N 이 나타 난 횟수 는 256 번 보다 적 으 며 알고리즘 을 설계 하고 효율 적 인 방식 으로 0 에서 65535 가 나타 난 횟수 를 큰 것 에서 작은 것 으로 정렬 해 야 합 니 다.
이 문제 의 관건 은 모든 숫자 가 나타 난 횟수 를 어떻게 기록 하 느 냐 하 는 것 이다. 어떤 사람들 은 Hashtable 을 생각 할 수도 있 고 심지어 자체 적 으로 데이터 구 조 를 구축 할 수도 있다. 예 를 들 어:
class Node
{
unsigned short int Num;
unsigned char Count;
};
그리고 하나의 vector < Node > 로 저장 하고 N 을 읽 을 때마다 vector 에서 Num = N 요 소 를 검색 하여 Count 를 1 로 추가 합 니 다.나타 나 지 않 았 다 면 노드 를 새로 추가 합 니 다.
방법 은 옳 습 니 다. 그러나 효율 이 매우 낮 습 니 다. 그 이 유 는 N 을 읽 을 때마다 검색 을 해 야 하기 때 문 입 니 다. 요 소 를 삽입 할 때 Num 크기 순 으로 배열 하 는 것 을 고려 하 더 라 도 요 소 를 검색 할 때 2 점 으로 찾 을 수 있 습 니 다. 그러나 효율 은 여전히 낙관적 이지 않 습 니 다. Hashtable 을 사용 하 는 상황 은 똑 같 습 니 다. 내부 검색 작업 만 숨겨 져 있 습 니 다.
가장 좋 은 방법 은 사실 매우 간단 하 다. 우 리 는 일반적인 unsigned char 배열 Times [65535] 를 만 들 면 된다.N 을 이 배열 의 액세스 색인 으로 하고 N 이 한 번 나타 날 때 Timers [N] 를 1 로 추가 합 니 다.이렇게 하면 입력 이 끝 날 때 우 리 는 배열 의 모든 요소 의 값 에 따라 대응 하 는 N 이 몇 번 나 타 났 는 지 알 수 있다.물론 뒤에 우리 가 정렬 과 출력 을 해 야 한 다 는 것 을 감안 하여 우 리 는 위 에서 정의 한 Node 구 조 를 사용 하여 배열 을 정의 할 수 있 습 니 다. 그러면 정렬 을 한 후에 우 리 는 해당 하 는 N 이 무엇 인지 알 수 있 습 니 다.