/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/fBcC
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.getTimer;
// @see http://projecteuler.net/index.php?section=problems&id=180
public class Euler180 extends Sprite {
private var _tf : TextField;
public function Euler180() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
NX.TF = _tf;
var s : int = getTimer();
tr(solve(35));
/*
var a : Array = [9343670, 151];
var b : Array = [270200, 7];
tr("a", a);
tr("b", b);
tr(GCDX(a, b).join("\n"));
*/
/*
var a : Array = [5772530, 1];
var b : Array = [4018200, 1];
tr("a", a);
tr("b", b);
tr(NX.div(a, b).join("\n"));
*/
var g : int = getTimer();
tr((g - s) + " ms");
}
// f_n(x,y,z)=(x+y+z)(x^n+y^n-z^n)と書ける。
// x+y+z>0なので、x^n+y^n-z^nなる有理数x,y,zを探せば良いが、
// フェルマーの大定理より、n=-2,-1,1,2以外の解は存在しないので、
// この4個について考えればよい。
private function solve(k : uint) : Array
{
var map : Object = {};
var uv : Array = [[0], [1]];
for(var a : uint = 1;a < k;a++){
for(var b : uint = a + 1;b <= k;b++){
if(GCD(a, b) != 1)continue;
for(var c : uint = a;c < k;c++){
for(var d : uint = c + 1;d <= k;d++){
if(GCD(c, d) != 1)continue;
var se : Number = Math.sqrt(a * a * d * d + b * b * c * c);
if(se == int(se)){
// n = 2
uv = judge(se, b * d, map, k, uv, a, b, c, d);
// n = -2
uv = judge(a * c, se, map, k, uv, a, b, c, d);
}
// n = 1
// ad+bc=bde/f
uv = judge(a * d + b * c, b * d, map, k, uv, a, b, c, d);
// n = -1
// ad+bc=acf/e
uv = judge(a * c, a * d + b * c, map, k, uv, a, b, c, d);
}
}
}
}
tr(uv[0]);
tr(uv[1]);
return NX.add(uv[0], uv[1]);
}
private var MAGIC : Number = 1000009;
private function judge(num : Number, den : Number, map : Object, k : uint, uv : Array, a : uint, b : uint, c : uint, d : uint) : Array
{
if(num < den){
var g : Number = GCD(num, den);
num /= g, den /= g;
if(den <= k){
var s : Array = addFractions(
[a, b], [c, d], [num, den]
);
if(!map[s[0] * MAGIC + s[1]]){
map[s[0] * MAGIC + s[1]] = 1;
uv = addFractionsX(uv, [[s[0]], [s[1]]]);
}
}
}
return uv;
}
private 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 : Number = ret[0] * o[i][1] + ret[1] * o[i][0];
var den : Number = ret[1] * o[i][1];
var g : Number = GCD(num, den);
ret[0] = num / g;
ret[1] = den / g;
}
return ret;
}
private function addFractionsX(...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 = NX.add(NX.mul(ret[0], o[i][1]), NX.mul(ret[1], o[i][0]));
var den : Array = NX.mul(ret[1], o[i][1]);
var g : Array = GCDX(num, den);
ret[0] = NX.div(num, g)[0];
ret[1] = NX.div(den, g)[0];
}
return ret;
}
private function GCDX(a : Array, b : Array) : Array
{
while(b.length > 1 || b[0] > 0){
var c : Array = a;
a = b;
b = NX.mod(c, b);
}
return a;
}
private function GCD(a : uint, b : uint) : uint
{
while(b > 0){
var c : uint = a;
a = b;
b = c % b;
}
return a;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
_tf.scrollV = _tf.maxScrollV;
}
}
}
import flash.text.TextField;
class NX{
public static const N : Number = 1E7;
public static var TF : TextField;
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(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;
}
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;
}
}
