1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 |
- #!/usr/bin/perl
- # Daniel "Trizen" Șuteu
- # Date: 11 October 2017
- # https://github.com/trizen
- # https://projecteuler.net/problem=435
- # Runtime: 0.990s
- use 5.010;
- use strict;
- use warnings;
- use ntheory qw(addmod mulmod powmod factor_exp factorial chinese);
- my @chinese;
- foreach my $p (factor_exp(factorial(15))) {
- my $n = 10**15;
- my $pp = $p->[0]**$p->[1];
- my $sum = 0;
- my ($f1, $f2) = (0, 1);
- my @array;
- foreach my $k (1 .. $n) {
- my $power_sum = 0;
- foreach my $x (1 .. 100) {
- $power_sum = addmod($power_sum, powmod($x, $k, $pp), $pp);
- }
- $sum = addmod($sum, mulmod($f2, $power_sum, $pp), $pp);
- push @array, $sum;
- ($f1, $f2) = ($f2, addmod($f1, $f2, $pp));
- if ($f1 == 0 and $f2 == 1 and $k > 20 and
- join(' ', @array[9 .. $#array/2])
- eq join(' ', @array[$#array/2 + 10 .. $#array])
- ) {
- $sum = $array[($n % $k) - 1];
- last;
- }
- }
- push @chinese, [$sum, $pp];
- }
- say chinese(@chinese);
|