const SMALL_PRIME = 665000; MAX_SMALL_PRIME = 10000001; THE_N = 109; MAX_K_POWER = 10; { Will check all k < 10^MAX_K_POWER } type SmallArray = array[1..SMALL_PRIME] of dword; Var pr, nn: SmallArray; c: dword; function PowMod(n, p : dword) : dword; const ONE: dword = 1; var tmp: dword; begin If (n <= 31) Then PowMod := (ONE shl n) mod p Else Begin tmp := PowMod(n div 2, p); asm movl tmp, %eax mull %eax divl p movl %edx, tmp end; If Odd(n) Then PowMod := (tmp + tmp) Mod p Else PowMod := tmp; end end; procedure TestK(k : qword); var i, p, x, k1, n, n2 : dword; begin For i := 4 To c do begin p := pr[i]; n := nn[i]; n2 := n + n; if n2 > p then n2 := n2 - p; {k1 := k Mod p;} asm movl k+4, %eax xorl %edx, %edx divl p movl k, %eax divl p movl %edx, k1 end; { x := k1 * nn[i] Mod p; } asm movl n, %eax mull k1 divl p movl %edx, x end; If (x = 1) Or (x = p-1) Then exit; x := x + x; If (x = p+1) Or (x = p-1) Then Exit; If (n = k1) Or (n2 = k1) Or (n + k1 = p) Or (n2 + k1 = p) Then Exit; end; writeln(k); end; Var i, j, p: Dword; pflag : Boolean; k,maxk: qword; begin pr[1] := 2; pr[2] := 3; pr[3] := 5; pr[4] := 7; pr[5] := 11; pr[6] := 13; pr[7] := 17; pr[8] := 19; c := 8; For i := 21 To MAX_SMALL_PRIME do begin if (i And 1) = 0 then continue; pflag := True; For j := 2 To c do begin p := pr[j]; If (i Mod p) = 0 Then begin pflag := False; break; End; If Word(p)*Word(p) > i Then break; End; If pflag Then begin c := c + 1; pr[c] := i; End; end; Writeln('c = ', c); For i := 4 To c do begin nn[i] := PowMod(THE_N, pr[i]); end; maxk := 1; for i:=1 to MAX_K_POWER do maxk := maxk * 10; k := 15; repeat TestK(k); k := k + 30; until k > maxk; end.