Сколько натуральных чисел вида 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
