как проверить делимость очень длинного числа в С++?

Как проверить делимость очень длинного числа в С++? я должен проверить, делится ли (3*n*n+3*n-1) на 2, 3 и 5 и n может быть до 10^ 10, поэтому long long int также сомнительно для работы, хотя я пытался сделать это:

unsigned long long int gg4,l;
gg4=(3*n*n+3*n-1);
if(gg4%3==0){
    gg4=gg4/3;
}
if(gg4%2==0){
    gg4=gg4/2;
}
if(gg4%5==0){
    gg4=gg4/2;
}

Но я думаю, это не сработает из-за диапазона n, поэтому, пожалуйста, помогите! :)

после этого мне также нужно разделить (3*n*n+3*n-1) на этот коэффициент, пожалуйста, помогите!


c++ long-integer modulo factorization
person naman    schedule 13.09.2014    source источник
comment
Оно никогда не будет делиться на 2, потому что либо 3*n*n нечетно, либо 3*n-1 нечетно. И на 3 никогда не делится. Остается только 5.   -  person harold    schedule 13.09.2014
comment
if(gg4% 5 ==0)gg4=gg4/ 2 опечатка?   -  person GingerPlusPlus    schedule 13.09.2014
comment
Ассортимент - проблема. 10 ^ 10 занимает ~ 33 бита, поэтому n * n занимает ~ 66 бит.   -  person david.pfx    schedule 13.09.2014

Ответы (1)


arrow_upward
3
arrow_downward

Чтобы расширить мой комментарий, есть два случая, когда (3*n*n+3*n-1) % 5 == 0, а именно

  • n = 5 * m + 1
  • n = 5 * m + 3

Для m целое число.

Так что на самом деле вам не нужно ничего долго вычислять, вы можете работать напрямую с n и вообще никогда не вычислять 3 * n * n + 3 * n - 1.

Просто проверьте:

n % 5 == 1 || n % 5 == 3
person harold    schedule 13.09.2014
comment
Значит, заданное домашнее задание было ошибкой? Кто бы мог подумать. - person david.pfx; 13.09.2014
comment
Поэтому просто проверьте, чтобы последняя цифра была 1, 3, 6 или 8. - person Jarod42; 13.09.2014