Matt Owen

source code for "files/pe/pe_048.pl"

return to portfolio
  1.  #!/usr/bin/perl
  2.  
  3.  use strict;
  4.  use warnings;
  5.  use bigint;
  6.  
  7.  
  8.  # raises $n to $p while modding by $mod between each step
  9.  # also... it does it the smart way.. more or less
  10.  sub pow_mod {
  11.   my ($n, $p, $mod) = @_;
  12.   my ($result) = 1;
  13.   my ($temp) = $n;
  14.  
  15.   my (@seq);
  16.   my ($k) = 0;
  17.  
  18.   while ($p) {
  19.   push @seq, $p%2;
  20.   $p/=2;
  21.   }
  22.  
  23.   for my $s (@seq) {
  24.   $temp = $n;
  25.   for (1..$k) {
  26.   $temp *= $temp % $mod;
  27.   }
  28.  
  29.   $result *= $temp % $mod if $s == 1;
  30.   $temp = $n % $mod;
  31.   $k++;
  32.  
  33.   }
  34.  
  35.   return $result % $mod;
  36.  }
  37.  
  38.  # init
  39.  my ($sum) = 0;
  40.  
  41.  
  42.  # work
  43.  for (1..1000) {
  44.   $sum += pow_mod($_, $_, 10**10);
  45.   $sum = $sum % 10**10;
  46.  }
  47.  
  48.  print $sum;