Trang chủ Tin Học Lớp 8 Hôm nay, anh Conan Kudo ngoan của chúng ta đang...

Hôm nay, anh Conan Kudo ngoan của chúng ta đang bị ốm, thế mà anh ta lại phải căng đầu để chiến đấu với 1 lời thách đố từ anh Quỳnh. Conankudo không thể giải đ

Câu hỏi :

Hôm nay, anh Conan Kudo ngoan của chúng ta đang bị ốm, thế mà anh ta lại phải căng đầu để chiến đấu với 1 lời thách đố từ anh Quỳnh. Conankudo không thể giải được vì anh ta đang lâm trọng bệnh, các bạn hãy thử giúp anh ta xem.
Sản phẩm số của 1 số nguyên dương là kết quả khi lấy tích của các chữ số tạo nên số nguyên đó. Ví dụ, sản phẩm số của 2612 là 2 * 6 * 1 * 2 = 24
Sản phẩm "bản thân" của 1 số là tích của nó với sản phẩm số. Ví dụ sản phẩm bản thân của 2612 là 2612 * 24 = 62688
Viết chương trình, biết 2 số nguyên dương A và B, tính số số nguyên dương có sản phẩm bản thân trong đoạn [A; B).
Input
Dòng duy nhất gồm 2 số nguyên A và B(1 <= A <= B <= 10 ^ 18)
Output
Chỉ gồm 1 số nguyên, là số số nguyên dương có kết quả trong khoảng [A; B).

c++ nhé :>

Lời giải 1 :

#include <bits/stdc++.h>
using namespace std;
 
const int LIM_P = 1e9;
const int LIM_D = 10;
const int LG = 32;
const int MAX_P = 5200;
 
int64_t power[LIM_D][LG];
int lim[LIM_D];
int num_prod;
int prod[MAX_P];
 
int64_t f[LG][MAX_P];
int num[LG], n;
 
void pre_prod() {
  for (int f : {2, 3, 5, 7}) {
    power[f][0] = 1;
    for (int i = 1; i < LG; i++) {
      if (power[f][i - 1] > LIM_P / f) {
        lim[f] = i - 1;
        break;
      }
      power[f][i] = power[f][i - 1] * f;
    }
    if (!lim[f]) {
      lim[f] = LG - 1;
    }
  }
 
  prod[++num_prod] = 0;
 
  for (int power_2 = 0; power_2 <= lim[2]; power_2++) {
    for (int power_3 = 0; power_3 <= lim[3]; power_3++) {
      if (power[2][power_2] > LIM_P / power[3][power_3]) {
        break;
      }
      for (int power_5 = 0; power_5 <= lim[5]; power_5++) {
        if (power[2][power_2] > LIM_P / power[3][power_3] / power[5][power_5]) {
          break;
        }
        for (int power_7 = 0; power_7 <= lim[7]; power_7++) {
          if (power[2][power_2] > LIM_P / power[3][power_3] / power[5][power_5] / power[7][power_7]) {
            break;
          }
          prod[++num_prod] = power[2][power_2] * power[3][power_3] * power[5][power_5] * power[7][power_7];
        }
      }
    }
  }
 
  sort(prod + 1, prod + 1 + num_prod);
}
 
int64_t dp (int idx, bool is_smaller, bool not_valid, int idx_p) {
  if (idx < 0) {
    return idx_p == 2;
  }
 
  if (is_smaller == true && not_valid == false && f[idx][idx_p] != -1) {
    return f[idx][idx_p];
  }
 
  int64_t ans = 0;
  int lim_d = is_smaller ? 9 : num[idx];
 
  for (int d = 0; d <= lim_d; d++) {
    bool new_smaller = is_smaller || d < lim_d;
    bool new_not_valid = not_valid && idx >= 1 && d == 0;
    if (new_not_valid) {
      ans += dp(idx - 1, new_smaller, new_not_valid, idx_p);
    }
    else {
      int real_p = prod[idx_p], new_idx_p;
      if (d == 0) {
        continue;
      }
      else if (real_p % d) {
        continue;
      }
      else
        real_p /= d;
      new_idx_p = lower_bound(prod + 1, prod + num_prod + 1, real_p) - prod;
      ans += dp(idx - 1, new_smaller, new_not_valid, new_idx_p);
    }
  }
 
  return is_smaller == true && not_valid == false ? f[idx][idx_p] = ans : ans;
}
 
int64_t calc (int64_t lim, int id_p) {
  if (lim < 0) return 0;
  n = 0;
  do {
    num[n++] = lim % 10;
    lim /= 10;
  } while (lim > 0);
 
  return dp(n - 1, false, true, id_p);
}
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
 
  pre_prod();
  memset(f, -1, sizeof(f));
 
  int64_t L, R; cin >> L >> R;
  int64_t ans = 0;
 
  for (int p = 2; p <= num_prod; p++) {
    int64_t low = (L + prod[p] - 1) / prod[p];
    int64_t high = R / prod[p];
 
    if (low > high) break;
 
    ans += calc(high, p) - calc(low - 1, p);
  }
 
  cout << ans;
  return 0;
}

Bạn có biết?

Tin học là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng. Tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin. Hãy tận dụng sức mạnh của tin học để giải quyết các vấn đề và sáng tạo ra những giải pháp mới!

Nguồn :

Wikipedia - Bách khoa toàn thư

Tâm sự lớp 8

Lớp 8 - Năm thứ ba ở cấp trung học cơ sở, học tập bắt đầu nặng dần và sang năm lại là năm cuối cấp, áp lực lớn dần. Hãy chú ý đến sức khỏe, cân bằng giữa học và nghỉ ngơi để đạt hiệu quả tốt nhất!

Nguồn :

sưu tập

Liên hệ hợp tác hoặc quảng cáo: gmail

Điều khoản dịch vụ

Copyright © 2021 HOCTAPSGK