Форум PHP

Да, вы правы. Любое число умноженное на число кратное 29 также будет кратно 29.

И ведь я когда написал скрипт вычисляющий перебором, видел этот ноль, но счел багом (исключением из правила) и подправил скрипт так чтоб ноль не получался =(

>Остаток произведения равен произведению остатков (Математика рулит!).

если так, то в списке этих чисел найдется несколько, которые делятся на 29 без остатка, т.е. с остатком 0. А значит и произведение общее - 0. В качестве доказательства необходимо найти хотя бы одно число из диапазона, удовлетворяющее условиям на сумму цифр и нацело делящееся на 29.

Function olimp29() {     For ($i=34482759; $i<68965517; $i++)    {         $arr_sum=array_sum(str_split($i*29));         if($arr_sum < 30 ) continue;         if($arr_sum > 40) continue;         Return $i*29;     } }

34482759* 29 = 1000000011 - начало диапозона
68965517*29 = 1999999993 - конец диапазона.
перебираем только числа, нацело делящиеся на 29.
Функция вернет первое число, соответствующее условиям. Время выполнения: 0.0012

хм, в свое время эксперементировал, да и логично предположить что если одно условие верно то второе не нужно проверять (если между ними стоит ИЛИ) доказательство.

if(true || echo123()) { echo 'эта строка будет выводиться'; } function echo123() { echo 'эта строка не будет выводиться'; }

не значительно, но на таких объемах.... Около секунды сэкономило. Просто в 1ом варианте проверяется 1 условие и если оно совпадает, то сразу переходит к следующему кругу, а во 2ом варианте проверяются всегда оба условия. Больше всего экономия на

$sum = $s[1]+$s[2]+$s[3]+$s[4]+$s[5]+$s[6]+$s[7]+$s[8]+$s[9];

только чтоб в пределах 30 секунд, мало будет того, что нужно составить перебор так чтоб не проверять цифры на соответствие условиям, но и как-то нужно будет исключить из вычислений около 90% подходящих под условия значений, т.к. по первому условию (от 30 до 40) подходит 11% всех чисел, а это 111 111 111 штук. Ну еще процентов 5 из них исключится по второму условию, пусть даже 10%, останется 100 миллионов, а 10 миллионов считаются 30 секунд. значит только на вычисления нужно 300 сек. Короче говоря ОООООООчень хотелось бы увидеть красивое решение =)

а разве так:

if($sum < 29) continue;  if($sum > 38) continue;

быстрее чем:

if($sum < 29 || $sum > 38) continue;

???

Даже не собираюсь спорить. Но и решения к сожалению не вижу. А хотелось бы увидеть!

я уже отправил олимпиаду, так что не актуально, и я вам точно могу сказать что программа должна выоплняться в переделах 30 сек

А если переписать вот так:

<?php   set_time_limit(0);   $startmicrotime = microtime(true);   $ost = 0;   for($i = 1000000000; $i < 1009999999; $i++){     $s = (string)$i;     if(substr_count($s,"5") > 1) continue;     $sum = $s[1]+$s[2]+$s[3]+$s[4]+$s[5]+$s[6]+$s[7]+$s[8]+$s[9];     if($sum < 29) continue;     if($sum > 38) continue;     $ost = $ost ? ($ost*($i%29))%29 : $i%29 ;   }   echo $ost."<br>".round(microtime(true)-$startmicrotime,4); ?>

то время сокращается почти в 2 раза

13 29.7928

а результат другой, т.к. в первый раз были заданы не правильные условия.

Ну на переборе только "правильных" чисел и обрубании "веток" я зашпарился, но учитывая пункт 2 предыдущего поста сделал так:

<?php   set_time_limit(0);   $startmicrotime = microtime(true);   $ost = 0;   for($i = 1000000000; $i < 1009999999; $i++){     $arr_sum=array_sum(str_split($i));     if($arr_sum < 30 || $arr_sum > 40) continue;     if(substr_count((string)$i,"5",1) > 1) continue;     if(!$ost) $ost = $i%29;     else $ost = ($ost*($i%29))%29;   }   echo $ost."<br>".round(microtime(true)-$startmicrotime,4); ?>

результат

18 55.4892

Значит до 1999999999 за 5500 секунд сосчитает =)