/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/wj1l
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.getTimer;
// @see http://projecteuler.net/index.php?section=problems&id=237
public class Euler237 extends Sprite {
private var _tf : TextField;
public function Euler237() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
var s : int = getTimer();
// tr(solve(1E12));
tr(solve(10));
var g : int = getTimer();
tr((g - s) + " ms");
}
private const M : int = 100000000;
private function solve(n : Number) : Number
{
var a : Array = [
[2, 2, 1E8-2, 1],
[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0]
];
var aa : Array = a;
var v : Array = [8, 4, 1, 1];
var i : Number, j : uint, k : uint;
if(n <= 3)return v[3 - n];
for(i = n - 4;i > 0;i = Math.floor(i / 2)){
if(i % 2 == 1){
var nv : Array = [0, 0, 0, 0];
for(j = 0;j < 4;j++){
for(k = 0;k < 4;k++){
nv[j] += mod(aa[j][k], v[k]);
}
}
for(j = 0;j < 4;j++){
v[j] = nv[j] % M;
}
}
aa = mul(aa, aa, M);
}
return v[0];
}
private function mul(a : Array, b : Array, m : uint) : Array
{
var h1 : uint = a.length;
var w1 : uint = b.length;
var w2 : uint = b[0].length;
var c : Array = new Array(h1);
var i : uint, j : uint, k : uint;
for(i = 0;i < h1;i++){
c[i] = new Array(w2);
for(j = 0;j < w2;j++){
var sum : Number = 0;
for(k = 0;k < w1;k++){
sum += mod(a[i][k], b[k][j]);
}
c[i][j] = sum % m;
}
}
return c;
}
private function mod(a : Number, b : Number) : Number
{
var r : Array = NX.mul(
[a%1E7, uint(a/1E7)],
[b%1E7, uint(b/1E7)]
);
var ret : Number = r[0];
if(r[1])ret += (r[1] % 10) * 1E7;
return ret;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
_tf.scrollV = _tf.maxScrollV;
}
}
}
class NX{
public static const N : Number = 1E7;
public static function add(a : Array, b : Array) : Array
{
var i : uint;
var minl : uint = Math.min(a.length, b.length);
for(i = 0;i < minl;i++){
a[i] += b[i];
}
for(i = a.length;i < b.length;i++){
a.push(b[i]);
}
carry(a);
return a;
}
public static function sub(a : Array, b : Array) : Array
{
var i : uint;
for(i = 0;i < b.length;i++){
a[i] -= b[i];
}
minuscarry(a);
shave(a);
return a;
}
public static function minuscarry(a : Array) : Array
{
for(var i : uint = 0;i < a.length;i++){
if(a[i] < 0){
var c : uint = (-a[i] + N - 1) / N;
a[i] += N * c;
a[i+1] -= c;
}
}
return a;
}
public static function mul(a : Array, b : Array) : Array
{
var ret : Array = new Array(a.length + b.length);
var i : uint, j : uint;
for(i = 0;i < ret.length;i++)ret[i] = 0;
for(i = 0;i < a.length;i++){
for(j = 0;j < b.length;j++){
ret[i + j] += a[i] * b[j];
}
}
carry(ret);
shave(ret);
return ret;
}
public static function mulint(a : Array, b : uint) : Array
{
for(var i : uint = 0;i < a.length;i++){
a[i] *= b;
}
carry(a);
return a;
}
public static function comp(a : Array, b : Array) : int
{
if(a.length != b.length)return a.length - b.length;
for(var i : int = a.length - 1;i >= 0;i--){
if(a[i] != b[i]){
return a[i] - b[i];
}
}
return 0;
}
public static function div(ao : Array, bo : Array) : Array
{
var p : Array = ao.concat();
if(ao.length - bo.length < 0){
return [0, p];
}
var b : Array = bo.concat();
p.push(0);
var d : Array = [];
for(var i : int = p.length - b.length - 1;i >= 0;i--){
var q0 : Number = Math.ceil((p[i + b.length] * N + p[i + b.length - 1]) / (b[b.length - 1] + (b[b.length - 2] || 0) / N));
var r : Array = b.concat();
r = mulint(r, q0);
while(true){
var le : Boolean = false;
for(var k : int = r.length;k >= 0;k--){
var pp : Number = p[i+k] || 0;
var rr : Number = r[k] || 0;
if(pp != rr){
le = pp < rr;
break;
}
}
if(le){
q0--;
sub(r, b);
}else{
break;
}
}
d.push(q0);
for(var j : uint = 0;j < r.length;j++){
p[j + i] -= r[j];
}
minuscarry(p);
}
d.reverse();
carry(d);
shave(d);
shave(p);
return [d, p];
}
public static function mod(ao : Array, bo : Array) : Array
{
var p : Array = ao.concat();
if(ao.length - bo.length < 0){
return p;
}
var b : Array = bo.concat();
p.push(0);
var d : Array = [];
for(var i : int = p.length - b.length - 1;i >= 0;i--){
var q0 : Number = Math.ceil((p[i + b.length] * N + p[i + b.length - 1]) / (b[b.length - 1] + (b[b.length - 2] || 0) / N));
var r : Array = b.concat();
r = mulint(r, q0);
while(true){
var le : Boolean = false;
for(var k : int = r.length;k >= 0;k--){
var pp : Number = p[i+k] || 0;
var rr : Number = r[k] || 0;
if(pp != rr){
le = pp < rr;
break;
}
}
if(le){
q0--;
sub(r, b);
}else{
break;
}
}
for(var j : uint = 0;j < r.length;j++){
p[j + i] -= r[j];
}
minuscarry(p);
}
shave(p);
return p;
}
public static function carry(a : Array) : Array
{
for(var i : uint = 0;i < a.length;i++){
if(a[i] >= N){
var c : uint = a[i] / N;
if(i == a.length - 1){
a.push(0);
}
a[i + 1] += c;
a[i] %= N;
}
}
return a;
}
private static function gcd(a : Array, b : Array) : Array
{
while(b.length > 1 || b[0] > 0){
var c : Array = a;
a = b;
b = mod(c, b);
}
return a;
}
public static function shave(a : Array) : Array
{
for(var i : uint = a.length - 1;i >= 1;i--){
if(a[i] > 0)break;
a.pop();
}
return a;
}
private static function addFractions(...o : Array) : Array
{
if(o.length == 0)return [[0], [1]];
var ret : Array = o[0].concat();
for(var i : uint = 1;i < o.length;i++){
var num : Array = add(mul(ret[0], o[i][1]), mul(ret[1], o[i][0]));
var den : Array = mul(ret[1], o[i][1]);
var g : Array = gcd(num, den);
ret[0] = div(num, g)[0];
ret[1] = div(den, g)[0];
}
return ret;
}
public static function pow(a : Array, b : uint) : Array
{
var ret : Array = [1];
var m : Array = a.concat();
for(var u : uint = b;u > 0;u >>= 1){
if(u & 1){
ret = mul(ret, m);
}
m = mul(m, m);
}
return ret;
}
}
