export class Divisors {
// 約数を求める （自分自身は含めない）
public static get(num: number): number[] {
let ary = [];
let m = Math.floor(num / 2);
for (let n = 1; n <= m; n++) {
if (num % n === 0) {
ary.push(n);
}
}
return ary;
}
}
友愛数を求める
このメソッドができれば、友愛数を求めるのはそれほど難しくありませんね。
import * as Utils from './utils';
import { Divisors } from './math/divisors';
class Solver {
exec(num: number): number {
return this.amicableNumbers(num).map(x => x[0] + x[1]).reduce((x, y) => x + y,0);
}
// n 未満の友愛数のペアを列挙する
private amicableNumbers(n: number): [number,number][] {
var amicables = [];
for (let a = 1; a < n; a++) {
let temp = Divisors.get(a);
let d = temp.reduce((x, y) => x + y,0);
if (a >= d)
continue;
let y = Divisors.get(d).reduce((x, y) => x + y,0);
if (a == y)
amicables.push([a, d]);
}
return amicables;
}
}
class Application {
static run(): void {
let sw = Utils.Stopwatch.startNew();
try {
let p = new Solver();
let n = p.exec(10000);
console.log(n);
} finally {
sw.stop();
console.log(sw.toString());
}
}
}
Application.run();
export class Divisors {
// 約数を求める （自分自身は含めない）
public static get(num: number): number[] {
let ary = [];
if (num == 1)
return ary;
ary.push(1);
let m = Math.floor(Math.sqrt(num));
if (m * m === num) {
ary.push(m);
m--;
}
for (let i = 2; i <= m; i++) {
if (num % i === 0) {
ary.push(i);
ary.push(Math.floor(num / i));
}
}
return ary;
}
}
const Fig: number = 10000000;
const Format: string = "000000";
const SliceNum: number = -7;
export class BigUInt {
private list: number[] = [];
constructor(n: number) {
let i = 0;
while (n > 0) {
this.list[i] = n % Fig;
n = Math.floor(n / Fig);
i++;
}
}
private create(src: number[]): BigUInt {
var obj = new BigUInt(0);
obj.list = src;
return obj;
}
public clone(): BigUInt {
var obj = new BigUInt(0);
for (var i = 0; i < this.list.length; i++)
obj.list[i] = this.list[i];
return obj;
}
public add(num: BigUInt): BigUInt {
let sum: number[] = [];
let carry = 0;
if (this.list.length > num.list.length) {
var a = this.list;
var b = num.list;
} else {
var a = num.list;
var b = this.list;
}
for (var i = 0; i < a.length; i++) {
if (i < b.length)
var n = a[i] + b[i] + carry;
else
var n = a[i] + carry;
sum[i] = n % Fig;
carry = Math.floor(n / Fig);
}
if (carry > 0)
sum[i] = carry;
return this.create(sum);
}
public multiple(num: BigUInt): BigUInt {
let ans = new BigUInt(0);
let wrk: number[] = [];
let a = this.list;
let b = num.list;
for (let ax = 0; ax < a.length; ax++) {
for (let i = 0; i < ax; i++)
wrk[i] = 0;
let carry = 0;
for (var bx = 0; bx < b.length; bx++) {
var n = a[ax] * b[bx] + carry;
wrk[bx + ax] = n % Fig;
carry = Math.floor(n / Fig);
}
wrk[bx+ax] = carry;
let w = this.create(wrk);
ans = ans.add(w);
}
return ans;
}
public toString() {
var s: string = "";
for (var i = this.list.length - 1; i >= 0; i--) {
var n = this.list[i];
s += (Format + n).slice(SliceNum);
}
return s.replace(/^0+/g, '');
}
}
import * as Utils from './utils';
import { BigUInt } from './math/bigUInt';
class Solver {
exec(maxnum: number): number {
var a = new BigUInt(1);
for (var i = 2; i <= maxnum; i++) {
a = a.multiple(new BigUInt(i));
}
return a.toString().split("")
.map(x => parseInt(x))
.reduce((x, y) => x + y);
}
}
class Application {
static run(): void {
let sw = Utils.Stopwatch.startNew();
try {
let p = new Solver();
let n = p.exec(100);
console.log(n);
} finally {
sw.stop();
console.log(sw.toString());
}
}
}
Application.run();
import * as Utils from './utils';
class Solver {
exec(year1: number, year2: number): number {
let count = 0;
let sunday = 0;
let dt = new Date(year1, 1-1, 1);
while (dt < new Date(year2, 12 - 1, 31)) {
dt.setMonth(dt.getMonth() + 1);
if (dt.getDay() == sunday)
count++;
}
return count;
}
}
class Application {
static run(): void {
let sw = Utils.Stopwatch.startNew();
try {
let p = new Solver();
let n = p.exec(1901,2000);
console.log(n);
} finally {
sw.stop();
console.log(sw.toString());
}
}
}
Application.run();
import * as Utils from './utils';
import { BigInt } from './math/bigInt';
class Solver {
exec(num: number): number {
var int = new BigInt(2);
for (var i = 1; i < num; i++) {
int = int.twice();
}
var s = int.toString();
return s.split("").map(x => parseInt(x)).reduce((x, y) => x + y);
}
}
class Application {
static run(): void {
let sw = Utils.Stopwatch.startNew();
try {
let p = new Solver();
let n = p.exec(1000);
console.log(n);
} finally {
sw.stop();
console.log(sw.toString());
}
}
}
Application.run();
import * as Utils from './utils';
class Solver {
exec(num: number): number {
let max = 0;
let ans = 0;
for (let n = num - 1; n > 0; n--) {
let collatz = this.nextCollatz(n);
let count = 2; // 数列の２番目までは求め終わっている
while (collatz !== 1) {
collatz = this.nextCollatz(collatz);
count++;
}
if (max < count) {
max = count;
ans = n;
}
}
return ans;
}
nextCollatz(n: number): number {
if (n % 2 === 0)
return n / 2;
return 3 * n + 1;
}
}
class Application {
static run(): void {
let sw = Utils.Stopwatch.startNew();
try {
let p = new Solver();
let n = p.exec(1000000);
console.log(n);
} finally {
sw.stop();
console.log(sw.toString());
}
}
}
Application.run();
class Solver {
// ハッシュテーブル
private known: { [key: number]: number } = [];
exec(num: number): number {
let max = 0;
let ans = 0;
for (let n = num; n > 0; n--) {
if (this.known[n] !== undefined)
continue;
let x = this.CollatzSequence(n);
let count = x[0];
let list = x[1];
if (max < count) {
max = count;
ans = n;
}
// let k = count;
while (list.length > 0) {
this.known[list.shift()] = count--;
}
}
return ans;
}
// シーケンスを生成し返す。 その時のシーケンスの数も返したいので、Tupleを返す
CollatzSequence(n:number) : [ number , Array<number> ] {
let seq: Array<number> = new Array();
let collatz = n;
let count = 0;
while (collatz !== 1) {
if (this.known[collatz] !== undefined) {
count += this.known[collatz];
break;
}
seq.push(collatz);
count++;
collatz = this.nextCollatz(collatz);
}
return [ count, seq ];
}
nextCollatz(n: number): number {
if (n % 2 === 0)
return n / 2;
return 3 * n + 1;
}
}
