SHARE
TWEET

Untitled

a guest Feb 17th, 2017 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. 1) N == target 이면 Yes,  N % target != 0 이면 No
  3. -> 자명
  4. 2) target이 소수면 Yes
  5. -> 자명
  6. 3) 어떤 소수 p에 대해 target == p^2 && N == p^k 를 만족하면 Yes
  7. -> 적절한 귀납법으로 답이 Yes라는 것을 증명할 수 있다.
  8. 4) 그 이외엔 No
  9. 4-1) target이 두 개 이상의 소인수를 갖고 있는 경우
  10. 4-2) 어떤 소수 p에 대해 target == p^k  (k>=3) 인 경우
  11. 4-3) 어떤 소수 p에 대해 target == p^2 && N != p^k 인 경우
  12. -> 모두 적절한 귀납법으로 답이 No라는 것을 증명할 수 있다.
  13. */
  14. #include <cmath>
  15. #include <string>
  16. using namespace std;
  17.  
  18. bool notPrime[100003];
  19.  
  20. class CompositeSmash {
  21. public:
  22.     void sieve() {
  23.         for (int i = 2; i <= 100000; ++i) {
  24.             if (notPrime[i]) continue;
  25.             for (int j = i + i; j <= 100000; j += i) notPrime[j] = true;
  26.         }
  27.     }
  28.  
  29.     string thePossible(int N, int target) {
  30.         if (N % target != 0) return "No";
  31.         if (N == target) return "Yes";
  32.         sieve();
  33.         if (!notPrime[target]) return "Yes";
  34.  
  35.         int pp = (int)(sqrt(target) + 1e-8);
  36.         for (; N % pp == 0; N /= pp);
  37.         if (!notPrime[pp] && pp * pp == target && N == 1) return "Yes";
  38.  
  39.         return "No";
  40.     }
  41. };
RAW Paste Data
Top