возникла проблема с A^B mod C

[frost_uw]

Условии задачи:

Вам даны целые числа A, B, C. Выведите остаток от деления A^B mod C.

Ограничения:

0 <= A, B <=10^18, 1 <= C <= 10^18

Ответом служит число, которое является остатком от деления.


з.ы. честно сказать озадачен, как это можно было бы реализовать....

[worm2]

Здесь нужно воспользоваться тем замечательным фактом, что для любых целых $A$, $B$, $C$ ($C \ne 0$) верно равенство:
$(A\cdot B) \pmod C=\left(\left(A \pmod C\right)\cdot\left(B\pmod C\right)\right)\pmod C$.

Правда, нужно ещё уметь перемножать целые числа до порядка $10^{18}$ (и получать ответ также в виде целого числа), а такая возможность не в каждую систему программирования встроена. Вам на чём нужно сделать эту задачку?

[frost_uw]

worm2 писал(а):

Здесь нужно воспользоваться тем замечательным фактом, что для любых целых $A$, $B$, $C$ ($C \ne 0$) верно равенство:
$(A\cdot B) \pmod C=\left(A \pmod C\right)\cdot\left(B\pmod C\right)$.

Правда, нужно ещё уметь перемножать числа порядка $10^{18}$, а такая возможность не в каждую систему программирования встроена. Вам на чём нужно сделать эту задачку?

на pascal'e желательно

хотя можно и на C/C++

вот как такие огромные числа представлять... Длинная арифметика? Может есть идеи, как это сделать

[worm2]

Да, здесь без длинной арифметики не обойтись. Причём нужно будет реализовать и умножение, и сложение 128-битных чисел, и деление с остатком 128-битного числа на 64-битное.

За основу можно взять знаковую 64-битную арифметику, которая встроена и в Pascal (Comp, Int64 в последних версиях Delphi) и в C (__int в Borland/MS, longlong int в GCC, про остальные не знаю).

[Yuri Gendelman]

frost_uw писал(а):

честно сказать озадачен, как это можно было бы реализовать...

Начните отсюда: Arbitrary-precision arithmetic.

[Nik_Svan]

frost_uw писал(а):

честно сказать озадачен, как это можно было бы реализовать

см.: http://www.intel.com/software/products/ ... /index.htm