Задача степень

[Lion_paint]

Вводится 3 числа n,k,p(1 ≤ N ≤ 10000, 1 ≤ K ≤ 100, 2 ≤ P ≤ 10^9)
требуется посчитать скмму k-х степеней первых n натeральных чисел взятых по модулю p
Пример
10 1 997 55

[Lion_paint]

задачи в Paskal

[Plague]

var s:int64;
    n,k,p,i:longint;
begin
readln(n,k,p);
s:=0;
for i:=1 to n do
  s:=s+(round(power(i,k)) mod p);
writeln(s);
end.

[puporev]

Жалко только что в Паскале нет ни Int64, ни Power.

[Plague]

У меня есть и Int64 и Power).
Это решение чтобы было оттолкнуться от чего.
Оно не совсем правильное, так как нет своих наработок.

[Sazary]

Имхо задача на длинную арифметику.
Только вот условие я что-то до конца не понял. А конкретно:

взятых по модулю p

И почему в примере 4 числа, когда вводятся только 3?

[puporev]

Четвертое число это результат, т.е. сумма первых 10 чисел в первой степени.

[Plague]

Можно обойтись и без "длинки" так как модуль есть.

[puporev]

Да, это задача не на длинную арифметику, а на соображаловку. У меня ее практически нет.

[Sazary]

Вот. Функцию подсмотрел на алголисте.
Вроде подходит.

uses crt;
var
n,k,p,i : longint;
sum : longint;

function powmod(a,k,n : longint) : longint;
 var b : longint;
 begin
 b := 1;
 while k<>0 do
  begin
  if k mod 2 = 0 then
   begin
   k := k div 2;
   a := (a*a) mod n;
   end
  else
   begin
   dec(k);
   b := (b*a) mod n;
   end;

  end;
 Result := b;
 end;

begin
clrscr;
sum := 0;
readln(n,k,p);
for i:=1 to n do
 sum := sum + powmod(i,k,p);
writeln('sum= ',sum);
readln;
end.