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é :>
#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;
}
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!
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!
Copyright © 2021 HOCTAPSGK