Блог пользователя alligator

Автор alligator, 13 лет назад, По-русски

Задача про совершенные числа . Вот ссылка .. отправляю решение , даёт ВА , столько стралася понять в чём проблема , не понял , вроде на все мои тесты выводит правильные ответы , теперь надеюсь на вашу помощь)

вот решение

#include<stdio.h>
#include<iostream>
using namespace std;
int main ()
             {
            long long n,m,i,j,cnt=0,r=0;
           cin>>n>>m;
          for (i=n;i<=m;i++)
               {cnt=0;
               for (j=1;j*j<=i;j++)
                   {
                    if (i%j==0){
                    cnt+=j; if (i/j > j && j!=1) {cnt+=i/j;}}
                   }
               if (cnt==i)
                  {r=1;
                  cout<<i<<"\n";
                   }
               }
          if (r==0)
           {
           printf ("Absent\n");
          }
          return 0;
        }

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Небось, 1 - совершенное? :)
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
1 - не совершенное число, т.к. по условию "Число называется совершенным, если оно равно сумме всех своих делителей, МЕНЬШИХ его самого". Сумма таких числителей у 1-цы равна нулю. В этом у вас и ошибка.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
if ( j!=1) {cnt+=i/j;}  - вот так должно быть.  Но в итоге и это не спасет от TL.  "M и N целые, 1 <= M <= N <= 109, (N - M) * sqrt(N) <= 107" Отсюда крайний случай, когда N - 109  и тогда N - M что, то около 103 * 3. Хотя там про время ничего не написано...   
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Все правильно у него было, только случай с единицей не рассмотрел. Сложность - как раз О((N-M)*sqrt(N)), что на макс. тесте - 10^7. Это почти в любой ТЛ уложится, в секунду-то точно.