PKU [2649]. Factovisors. [AC]

#include <stdio.h> #include <math.h> int chkPrime(int m); int main() { int n, m, i; int result; while(scanf("%d%d", &n, &m) != EOF) { if(m != 0) { if((m < n) || (n == m) || (n == 0 && m == 1)) { printf("%d divides %d!\n", m, n); continue; } else { if(chkPrime(m) == 1) { printf("%d does not divide %d!\n", m, n); continue; } result = m; for(i=2 ; ; i+=2) { result /= 2; if(chkPrime(result) == 1 && result > n) { printf("%d does not divide %d!\n", m, n); break; } else if(result < n) { printf("%d divides %d!\n", m, n); break; } } } } else { printf("%d does not divide %d!\n", m, n); continue; } } return 0; } int chkPrime(int m) { int i; if(m <= 1) { return 1; } else if(m == 2 || m % 2 == 0) { return 0; } for(i=3 ; i<=sqrt(m) ; i+=2) { if(m % i == 0) { return 0; } } return 1; }

In PKU judge System.

으허허. 드디어 AC 입니다. -_-!

이거 붙잡고 있느라 포스트도 제껴버렸군요 -_-;;;;;

크흠. 의외로 정말 간단한 문제였습니다.

n 과 m을 비교해서 m 이 n 보다 작거나 같을 경우는 무조건 나눌 수 있습니다.

이 경우 체크해야 하는 것은 m 이 n 보다 큰 경우지요.
이때 m 이 소수라면 무조건 이 수는 n 을 나눌 수 없습니다. -_-;

따라서, m 을 2로 나누어 가면서 최종적으로 m 이 n 보다 작은 수라면 - 소수건, 그렇지 않건 관계 없이. -나눌 수 있습니다.
그러나 만약 이 루틴에서 m 이 n 보다 큰 소수라면, 나눌 수 없겠죠. -_-!;
- 만약 반례가 있다면 알려주세요. -

자... 그럼 진짜로 '오늘'은 Heap 포스트와 검색 알고리즘 포스트가 올라갑니다. -_-;;;;;;

빌어먹을.... 졸려 죽겠네요 -_-;;;; 지금 3시 50분입니다. 좀 자야겠어요.