BOJ 1979 - 극적인 곱셈

BOJ 1979 - 극적인 곱셈

이 문제는 Parasitic number 에 대한 내용이지만, 그런거 몰라도 풀 수 있다.

일정 상한을 두고 루프를 돌려보면 된다.

나는 이것저것 검사하는 코드를 썼으므로 $O(N^2)$ 로 풀 수 있는 문제이다.

그러니까 1000번 째 자리까지 다 검사해보자.

bigint 를 써야할 것이다.

---

$10^0$ 자리가 $k$ 라는 것은, $nk$ 의 $10^0$ 자리 수가 $10^1$ 자리 수가 된다는 것을 의미한다.

비슷한 방식으로 계속해서 숫자들을 특정해나갈 수 있다.

현재까지의 구한 정답을 검사해보고 정답이되는 수라면 출력하고 아니면 길이 1000까지 다 검사해보고 안나온다면 0을 출력해주는것으로 문제를 해결할 수 있다.

bigint pw10[1000] = {1};  
  
void solve(int n, int k) {  
   for (int i = 1; i < 1000; i++) pw10[i] = pw10[i - 1] * 10ll;  
  
   bigint ans = k;  
  
   auto chk = [&](bigint c) {  
      bigint nxt = c * bigint(n);  
      string cc = c.to_string();  
      string nn = nxt.to_string();  
  
      if (sz(cc) == sz(nn)) {  
         for (int i = 0; i < sz(cc); i++) {  
            if (cc[i] == nn[md(sz(cc), i + 1)]) {  
  
            } else return 0;  
         }  
         return 1;  
      } else return 0;  
   };  
  
   bool not_found = 0;  
   function<void(int)> fn = [&](int i) -> void {  
      if (i >= 1000) {  
         not_found = 1;  
         return;  
      }  
      int answered = chk(ans);  
      if (answered) return;  
      bigint nxt = ans * n;  
      nxt = nxt % pw10[i];  
      nxt /= pw10[i - 1];  
      ans += nxt * pw10[i];  
      fn(i + 1);  
   };  
   fn(1);  
   if (not_found) cout << 0 << endl;  
   else {  
      cout << ans;  
      //cout << ans << endl << ans * n << endl;  
   }  
  
}