Так что это был вопрос по одной из проблем, с которыми я столкнулся в онлайн -конкурсе, несколько дней назад. < /p>
Вопрос: < /strong> < /p>
Примите два входа. < /p>
Большое количество n < /em> < /strong> цифры, < /li>
Количество вопросов q следует задать. < /li>
< /ol>
В каждом из вопросов вы должны найти, если число, сформированное по строке между индексами l < /em> i и r i делится на 7 или нет.
input:
Первая строка содержит число, состоящее на n < /em> < /strong> цифрах. Следующая строка содержит Q , обозначая количество вопросов. Каждая из следующих линий Q содержит 2 целых числа l i < /sub> и r i .
output: < /strong> < /p>
Для каждого вопроса печатайте «Да» или «Нет», если число, сформированное Строка между индексами l i и r i делится на 7.
Ограничения: < /strong> < /p>
1 ≤ n ≤ 10 5 < /sup> < /p>
1 ≤ q ≤ 10 5
1 ≤ l i , r i ≤ N < /p>
Примерный ввод: < /strong> < /p>
357753
3
1 2
2 3
4 4
< /p>
Вывод образца: < /strong> < /p>
Да
no
yes
< / p>
Объяснение: < /strong> < /p>
Для первого запроса число будет 35, что явно делится по 7. < /p>
ограничение времени: < /em> < /strong> 1,0 с для каждый входной файл. < /p>
Предел памяти: < /em> < /strong> 256 Mb < /p>
< Strong> исходный предел: < /em> < /strong> 1024 кб < /p>
Мой подход :
Теперь в соответствии с ограничениями, максимальная длина числа, т.е. n может быть до 10 5 . Это большое число не может быть включено в числовую структуру данных, и я уверен, что это не эффективный способ сделать это. strong> < /p>
Я подумал об этом алгоритме, чтобы применить общие правила деления к каждой отдельной цифровой цифре числа. Это будет работать, чтобы проверить делительность среди любых двух чисел, в линейное время, то есть o (n) < /strong>. < /P>
static String isDivisibleBy(String theIndexedNumber, int divisiblityNo){
int moduloValue = 0;
for(int i = 0; i < theIndexedNumber.length(); i++){
moduloValue = moduloValue * 10;
moduloValue += Character.getNumericValue(theIndexedNumber.charAt(i));
moduloValue %= divisiblityNo;
}
if(moduloValue == 0){
return "YES";
} else{
return "NO";
}
}
< /code>
Но в этом случае алгоритм должен также пройти через все значения q < /strong>, которые также могут быть до 10 5 .
Следовательно, время, необходимое для решения проблемы, становится o (q.n) , которое также может рассматриваться как квадратичное время . Следовательно, это пересекало заданное ограничение по времени и было не эффективно.
second try: < Br />
После этого я не сработал, я попытался искать правило разделимости 7 < /strong>. Все те, которые я нашел, включали расчеты, основанные на каждой отдельной цифре числа. Следовательно, это снова приведет к алгоритму линейного времени. И, следовательно, в сочетании с количеством вопросов, это будет составлять квадратичное время, то есть o (Q.n) < /strong> < /p>
Я нашел один алгоритм именовано метод делимости Pohlman -Mass на 7 < /strong>, который предположил < /p>
Использование быстрых чередующихся добавлений и вычитаний:
42,341,530
-> 530 -341 = 189 + 42 = 231 -> 23 -(1 × 2) = 21 Да < /p>
< /blockquote>
< P> Но все, что это сделало, это было время 1/3 Q.N, что не очень помогло. < /p>
Я что -то здесь упускаю? Может ли кто -нибудь помочь мне найти способ решить это?>
Подробнее здесь: https://stackoverflow.com/questions/386 ... sible-by-7
