95 lines
2.5 KiB
Zig
95 lines
2.5 KiB
Zig
const std = @import("std");
|
|
|
|
const stdout = std.io.getStdOut().writer();
|
|
|
|
fn print(comptime str: []const u8, args: anytype) void {
|
|
stdout.print(str, args) catch unreachable;
|
|
}
|
|
|
|
fn println(comptime str: []const u8, args: anytype) void {
|
|
print(str ++ "\n", args);
|
|
}
|
|
|
|
//const n: u512 = 7405872386298001828045412304885395957447735855540402226273272018863616985100578690399814241980651881616439657049448993379923363875365701026162288146836853;
|
|
|
|
const n: u512 = 70666344586694209770041979947;
|
|
//const n: u512 = 77;
|
|
|
|
var sqrt: u512 = undefined;
|
|
|
|
fn base3Mask(val: u512, size: usize) u512 {
|
|
return val % std.math.pow(u512, 10, size);
|
|
}
|
|
|
|
var nBase: []u512 = undefined;
|
|
|
|
pub fn main() !void {
|
|
var alloctor = std.heap.ArenaAllocator.init(std.heap.page_allocator);
|
|
defer alloctor.deinit();
|
|
|
|
var alloc = alloctor.allocator();
|
|
|
|
var size_n: usize = std.math.log10_int(n) + 2;
|
|
|
|
nBase = try alloc.alloc(u512, size_n);
|
|
|
|
for (0..size_n) |i| {
|
|
nBase[i] = base3Mask(n, i + 1);
|
|
}
|
|
|
|
searchPackAccStart(1);
|
|
}
|
|
|
|
fn searchPackAccStart(acc: u64) void {
|
|
for (0..10) |_i| {
|
|
var i: u512 = _i;
|
|
for (0..10) |_j| {
|
|
var j: u512 = _j;
|
|
var mul: u512 = i * j;
|
|
if (mul == n) {
|
|
println("Found them {} {}!", .{ j, i });
|
|
std.os.exit(1);
|
|
}
|
|
if (mul > n) break;
|
|
var mulMask = base3Mask(mul, acc);
|
|
|
|
if (mulMask == nBase[acc - 1]) {
|
|
searchPackAcc(acc + 1, i, j, 10, 10);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
fn searchPackAcc(acc: u64, n1: u512, n2: u512, _size_n1: u512, _size_n2: u512) void {
|
|
var size_n1 = _size_n1;
|
|
var size_n2 = _size_n2;
|
|
for (0..10) |_i| {
|
|
var i = _i * _size_n1 + n1;
|
|
size_n2 = _size_n2;
|
|
for (0..10) |_j| {
|
|
var j = _j * _size_n2 + n2;
|
|
var mul: u512 = i * j;
|
|
if (mul > n) break;
|
|
if (mul == n) {
|
|
if (i == 1 or j == 1) {
|
|
break;
|
|
}
|
|
println("Found them {} {}!", .{ j, i });
|
|
std.os.exit(1);
|
|
}
|
|
var mulMask = base3Mask(mul, acc);
|
|
|
|
if (mulMask == nBase[acc - 1]) {
|
|
println("trying {} {}-{}({}) {}-{}({}) {}", .{ acc, _i, i, _size_n1, _j, j, _size_n2, mul });
|
|
searchPackAcc(acc + 1, i, j, size_n1, size_n2);
|
|
}
|
|
if (_j == 0) {
|
|
size_n2 *= 10;
|
|
}
|
|
}
|
|
if (_i == 0) {
|
|
size_n1 *= 10;
|
|
}
|
|
}
|
|
}
|