Как проверить деление на 7 для большого числа в C ++?

Question

Я должен проверить, если данное число делится на 7, что обычно делается просто, делая что-то вроде n % 7 == 0, но проблема в том, что данное число может иметь до 100000000, что не подходит даже в long long.

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

Я ожидаю, что число будет на stdin, а вывод будет 1 / 0.

Это пример

34123461273648125348912534981264376128345812354821354127346821354982135418235489162345891724592183459321864592158
0

Должно быть возможно использовать только около 7 целочисленных переменных и cin.get(). Это также следует делать с использованием только стандартных библиотек.

Answer 1

вы можете использовать известное правило о делении на 7, которое гласит: сгруппируйте каждые 3 цифры, начиная справа, и начните вычитать и складывать их попеременно, делимость результата на 7 такая же, как и у исходного числа:

пример:

testing 341234612736481253489125349812643761283458123548213541273468213
        549821354182354891623458917245921834593218645921580

   (580-921+645-218+593-834+921-245+917-458+623-891+354-182
    +354-821+549-213+468-273+541-213+548-123+458-283+761-643
    +812-349+125-489+253-481+736-612+234-341 
    = 1882 )
    % 7 != 0 --> NOK!

Существуют и другие альтернативы этому правилу, которые легко реализовать.

Answer 2

Подумайте, как вы делите на бумаге. Вы смотрите на первую цифру или две и записываете кратное семи, записываете остаток и так далее. Вы можете сделать это с любым произвольным номером длины, потому что вам не нужно загружать все число в память.

Answer 3

Большинство делимых на семь правил работают на уровне цифр, поэтому у вас не должно возникнуть проблем с их применением к вашей строке.

Answer 4

Вы можете вычислить значение числа по модулю 7.

То есть для каждой цифры d и значения n, вычисленного до сих пор, n = (10 * n + d)% 7.

Преимущество заключается в том, что он работает независимо от делителя 7 или основания 10.

Answer 5

Вы можете вычислить значение числа по модулю 7.

То есть для каждой цифры d и значения n, вычисленного до сих пор, n = (10 * n + d)% 7.

Преимущество заключается в том, что он работает независимо от делителя 7 или основания 10.

Я решил эту проблему точно так же на одном из соревнований по программированию. Вот фрагмент кода, который вам нужен:

int sum = 0;
while (true) {
  char ch;
  cin>>ch;
  if (ch<'0' || ch>'9') break; // Reached the end of stdin
  sum = sum*10; // The previous sum we had must be multiplied
  sum += (int) ch;
  sum -= (int) '0'; // Remove the code to get the value of the digit
  sum %= 7; 
}

if (sum==0) cout<<"1";
else cout<<"0";

Этот код работает благодаря простым правилам модульной арифметики. Это также работает не только для 7, но фактически для любого делителя.

Answer 6

Я бы начал с вычитания большого числа, которое делится на 7.

Примеры чисел, которые делятся на 7, включают 700, 7000, 70000, 140000000, 42000000000 и т. Д.

В приведенном вами конкретном примере попробуйте вычесть 280000000000 (некоторое количество нулей) 0000.

Еще проще реализовать, многократно вычитать максимально возможное число, например 70000000000 (некоторое количество нулей) 0000.

Answer 7

Сначала возьмите это большое число в строку, а затем сложите каждую цифру строки. при последней проверке, если (сумма% 7 == 0)

Код:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,i,j,sum,k;
    sum=0;
    string s;
    cin>>s;
    for(i=0;i<s.length();i++)
    {
        sum=sum+(s[i]-'0');
    }

    if(sum%7==0)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }

    return 0;
}

Answer 8

Вот простой способ проверить делимость на 7:

Умножьте каждую цифру, начинающуюся справа от данного числа, на соответствующую цифру в этом шаблоне [1,3,2,6,4,5] (или [1,3,2, -1, -3 , -2]). Повторите шаблон при необходимости. Если сумма произведений делится на 7, то и исходное число тоже.

Пример: 2016 (6 * 1 + 1 * 3 + 0 * 2 + 2 * 6 = 21) делится на 7, так как 21 делится на 7.

См. Правила делимости .

Answer 9

N = abc

Существует простой алгоритм проверки, если трехзначное число кратно 7:

Замените a на x и добавьте его в bc, будучи x десятками двузначного числа, кратного 7, сотня которого равна.

N = 154; х = 2; 2 + 54 = 56; 7 | 56 и 7 | 154

N = 931; х = 4; 4 + 31 = 35; 7 | 35 и 7 | 931

N = 665; х = 5; 5 + 65 = 70; 7 | 70 и 7 | 665

N = 341; х = 6; 6 + 41 = 47; 7л47 и 7л341

Если N образовано различными периодами, обратная добавка результата одного периода должна быть добавлена ​​к сумме следующего периода следующим образом:

N = 341,234

6 + 41 = 47; - 41 мод 7 ≡ 1; 1 + 4 + 34 = 39; 7–39 и 7 • N

N = 341,234,612,736,481

Результат для 341.234 равен 39. Продолжая этот результат, мы имеем:

-39 мод 7 × 3; 3 + 5 + 6 + 1 + 2 + 1 = 18; - 18 мод 7 ≡ 3; 3 + 0 + 36 = 39; - 39 мод 7 ≡ 3; 3 + 1 + 81 = 85; 7-885 * 710

Это правило может быть применено полностью посредством умственного расчета и очень быстро. Это было получено из другого правила, которое я создал в 2.005. Он работает для чисел любой величины и делимости на 13.

Answer 10

Поскольку я недавно работал над разбивкой чисел, я намекаю, что для получения конкретных чисел - что вам понадобится в некоторых других ответах - подумайте о целочисленном делении и использовании модуля для получения из него цифр. .

Если бы у вас было меньшее число, скажем 123, как бы вы получили 1, 2 и 3 из него? Тем более что ты работаешь на базе 10 ...