Сколько натуральных чисел вида 2^a*3^b*5^c (a,b,c — неотрицательные целые числа) принадлежат отрезку [M;N]?
Входные данные
2 целых числа M и N. Каждое из чисел не превышает по абсолютному значению 10000.
Выходные данные
Вывести одно число — искомое количество чисел.
Пример
Вход: 10 20
Выход: 6
Идеи реализованного мной алгоритма:
1) рассмотреть частные случаи задачи (реализовано через if);
2) для случаев похожих на пример, вычислить сколько чисел удовлетворяет условию, например, от 1 до 10, от 1 до 20 и из большего количества вычесть меньшее;
3) процес вычисления количества чисел, удовлетворяющих условию на отрезке от 1 до N (или от 1 до M), производится на основ перебора значений (тройным циклом).
| | Программа |
| | #include <stdio.h>
#include <algorithm>
using namespace std;
int cntNumb(int x);
inline int absi(int x){ return x<0? -x : x;}
//----------------------------------------
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int M, N;
scanf("%d%d", &M, &N);
if(N==0 && M==0){
printf("0\n");
return 0;
}
if(N==M){
N = absi(N);
while(N>1 && N%2==0) N /= 2;
while(N>1 && N%3==0) N /= 3;
while(N>1 && N%5==0) N /= 5;
if(N==1) printf("1\n");
else printf("0\n");
return 0;
}
int cnt_M = cntNumb(absi(M));
int cnt_N = cntNumb(absi(N));
if(N==0){
printf("%d\n", cnt_M);
return 0;
}
if(M==0){
printf("%d\n", cnt_N);
return 0;
}
if(N*M>0){
printf("%d\n", absi(cnt_N-cnt_M)+1);
return 0;
}
if(N*M<0){
printf("%d\n", cnt_N+cnt_M);
return 0;
}
return 0;
}
//----------------------------------------
int cntNumb(int x){
int cnt(0);
int d2(1);
while(d2<=x){
int d3(1);
while(d2*d3<=x){
int d5(1);
while(d2*d3*d5<=x){
++cnt;
d5 *= 5;
}
d3 *= 3;
}
d2 *= 2;
}
return cnt;
}
|
| | |
Проблема: не проходит 2 теста из 6.
Какие случаи не учтены в программе?
Сайт для проверки программы
Код задачи DEMO_B
Здравствуйте, olimp_20, Вы писали:
_>Какие случаи не учтены в программе?
да вы какую-то фигню вообще считаете, вот попробуйте что-то типа
#include <stdio.h>
#include <algorithm>
bool is_ok(int a){
while(!(a % 5))
a = a / 5;
while(!(a % 3))
a = a / 3;
while(!(a % 2))
a = a / 2;
return a == 1;
}
int cnt(int from, int to){
int c = 0;
for(; from <= to; ++ from)
if(is_ok(from))
++c;
return c;
}
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int M, N;
scanf("%d%d", &M, &N);
printf("%d\n", cnt(M, N));
}
Здравствуйте, T4r4sB, Вы писали:
TB>Шо, так можно что ли. Это же брутфорс наглый.
Так в расчёте на брутфорс и сделаны условия: "до 10тыс".
Я даже больше скажу: если программа должна быстро обработать стопятьсот запросов, то можно один раз посчитать (даже во время компиляции) табличку
const int num_okays_table[10002]; // количество нужных чисел на интервале [0;i) для i = 0..10001
int num_okays(int M, int N) {
assert(0 <= M && M <= N && N <= 10000);
return num_okays_table[N+1] - num_okays_table[M];
}
Перекуём баги на фичи!
