看雪2023 KCTF年度赛 | 第11题·步步逼近-设计思路及解析
2023-9-30 16:51:59 Author: mp.weixin.qq.com(查看原文) 阅读量:5 收藏

这是一场人类与超智能AI的“生死”较量

请立刻集结,搭乘SpaceX,前往AI控制空间站

智慧博弈  谁能问鼎

看雪·2023 KCTF 年度赛于9月1日中午12点正式开赛!比赛基本延续往届模式,设置了难度值、火力值和精致度积分。由此来引导竞赛的难度和趣味度,使其更具挑战性和吸引力,同时也为参赛选手提供了更加公平、有趣的竞赛平台。

*注意:签到题持续开放,整个比赛期间均可提交答案获得积分

今日中午12:00第十一题《步步逼近》已截止答题,该题仅有xxx支战队成功提交flag,一起来看下该题的设计思路和解析吧。

出题团队简介

出题战队:中娅之戒

战队成员:iiiiiiiiiiii、海风月影、ww-rm

设计思路

题目分析

输入与结果

简单试错以及使用 IDA 获取伪代码可以知道题目的输入是一个不超过 10 位的十进制数字, 并且将范围限制在了 4K (0x1000) 至 4G (0x100000000) 之间 (包含两头端点). 所以解出此题的关键在于弄清楚题目如何对输入的数字进行验证。

/***** 省略前文 *****/
printf("Please input: ");
v0 = 0;
while ( 1 )
{
v1 = _getchar();
if ( v1 == 10 )
break;
v2 = v0 + 1;
_Buffer[v0] = v1;
if ( v0 + 1 >= 0xB )
goto LABEL_43;
_Buffer[v2] = 0;
if ( v0 == 9 && _getchar() != 10 )
goto LABEL_41;
++v0;
if ( v2 >= 10 )
goto LABEL_10;
}
if ( v0 >= 0xB )
{
LABEL_43:
__report_rangecheckfailure();
__debugbreak();
JUMPOUT(*(_DWORD *)__security_check_cookie);
}
_Buffer[v0] = 0;
LABEL_10:
v3 = 0;
if ( _Buffer[0] )
{
while ( ++v3 <= 10 )
{
if ( !_Buffer[v3] )
goto LABEL_15;
}
v3 = -1;
}
LABEL_15:
if ( sscanf_s(_Buffer, "%lld", &x) == 1 )
{
v4 = sprintf_s(v18, 0xBu, "%lld", x);
if ( v3 > 0 && v4 > 0 && v3 == v4 )
{
v5 = 0;
while ( _Buffer[v5] == v18[v5] )
{
if ( ++v5 >= v3 )
{
if ( SHIDWORD(x) >= 0 && (SHIDWORD(x) > 0 || (_DWORD)x) )
{
v6 = FindWindowW(L"OLLYDBG", 0);
v7 = HIDWORD(x);
v8 = x;
if ( v6 )
{
v8 = x | 0xFFFF;
LODWORD(x) = x | 0xFFFF;
}
if ( __PAIR__(HIDWORD(x), v8) - 4096 <= 0xFFFFF000 )
/***** 省略后文 *****/

如果输入错误, 则弹框提示Wrong answer!, 输入正确则弹框提示Accepted!。

/***** 省略前文 *****/
MessageBoxW(0, L"Accepted!", L"Result", 0x40u);
return 0;
}
}
}
}
}
break;
}
}
}
}
LABEL_41:
MessageBoxW(0, L"Wrong answer!", L"Result", 0x10u);
/***** 省略后文 *****/

验证机制

程序只有一些简单的反调试检测, 没有太多 anti, 主要难度还是在算法原理上, 因此可以比较容易逆向出算法流程和对应的伪代码。

核心部分是一个编码算法和一个解码算法, 而输入的序列号是两个算法的参数, 程序通过对随机输入进行编码与解码操作, 并检测是否能正确还原出原始输入序列来判断序列号是否正确。

用 IDA 可以还原出编码和解码算法的伪代码如下:

编码部分

/***** 省略前文 *****/
while ( 1 )
{
v51 = v16;
v43 = v15;
if ( v18 >= 10000 && (v15 < 0 || v15 <= 0 && !v16) )
break;
if ( v19 >= 20000 )
{
LABEL_38:
WaitForSingleObject(g_worker_mutex, 0xFFFFFFFF);
g_has_error = 1;
ReleaseMutex(g_worker_mutex);
v2 = v49;
goto LABEL_39;
}
if ( v18 >= 10000 )
{
v22 = *(_DWORD *)&v14[4 * v19];
v23 = __PAIR__(v15, v16) % v22;
HIDWORD(v53) = HIDWORD(v23);
v24 = __PAIR__(v15, v51) / v22;
v15 = (unsigned __int64)(__PAIR__(v15, v51) / v22) >> 32;
v16 = v24;
v14 = v45;
*(_DWORD *)&v50[4 * v19++] = v23;
v18 = v46;
v17 = (int)v40;
}
else
{
v20 = *v40 + *(_DWORD *)(v17 + v54) * __PAIR__(v15, v16);
v15 = HIDWORD(v20);
v55 = v20;
v39 = *(_DWORD *)&v45[4 * v19];
v16 = v20;
v53 = (signed __int64)__PAIR__(v43, v51) % v39;
if ( (signed __int64)((signed __int64)__PAIR__(v43, v51) / v39 * v20) < (signed __int64)__PAIR__(v56, v58) )
{
v18 = v46 + 1;
v14 = v45;
v17 = (int)(v40 + 1);
goto LABEL_12;
}
v21 = (signed __int64)__PAIR__(v43, v51) / v39;
v15 = v21 >> 32;
v16 = v21;
v14 = v45;
*(_DWORD *)&v50[4 * v19++] = v53;
v18 = v46;
v17 = (int)v40;
}
}
/***** 省略后文 *****/

解码部分

/***** 省略前文 *****/
while ( 1 )
{
v54 = v30;
v52 = v27;
if ( v25 < 0 && (v27 < 0 || v27 <= 0 && !v30) )
break;
if ( v28 < 0 )
goto LABEL_38;
if ( v25 < 0 )
{
v34 = *((_DWORD *)in_r + v28);
HIDWORD(v53) = (unsigned __int64)(__PAIR__(v27, v54) % v34) >> 32;
v35 = __PAIR__(v27, v54) / v34;
v27 = (unsigned __int64)(__PAIR__(v27, v54) / v34) >> 32;
v30 = v35;
v33 = (unsigned int)(__PAIR__(v52, v54) % v34) == v49[v28];
LABEL_34:
if ( !v33 )
goto LABEL_38;
v25 = v47;
--v28;
v29 = (int)v41;
v26 = v44;
}
else
{
v31 = *(_DWORD *)v41 + *(_DWORD *)(v26 + v29) * __PAIR__(v27, v30);
v27 = HIDWORD(v31);
LODWORD(v53) = v31;
v32 = *((_DWORD *)in_r + v28);
v30 = v31;
v55 = __PAIR__(v52, v54) % v32;
b_high = (unsigned __int64)(__PAIR__(v52, v54) / v32) >> 32;
b_low = __PAIR__(v52, v54) / v32;
if ( (signed __int64)(__PAIR__(v52, v54) / v32 * v31) >= *(_QWORD *)parameters )
{
v30 = b_low;
v27 = b_high;
v33 = v55 == v49[v28];
goto LABEL_34;
}
v25 = v47 - 1;
v26 = v44;
v29 = (int)(v41 - 4);
--v47;
v41 -= 4;
}
}
/***** 省略后文 *****/

算法流程不是太复杂, 可以看出是一种自定义的混合进制编解码算法, 而输入的序列号作为参数来控制算法正确运行, 算法涉及到的关键参数如下图:

/***** 省略前文 *****/
in_r = _calloc(10000u, 4u);
in = _calloc(10000u, 4u);
v2 = in;
v49 = in;
out_r = (char *)_calloc(20000u, 4u);
v4 = out_r;
v45 = out_r;
out = (char *)_calloc(20000u, 4u);
/***** 省略片段 *****/
b_low = *(_DWORD *)parameters;
v17 = (int)v49;
b_high = *((_DWORD *)parameters + 1);
/***** 省略后文 *****/

b: 输入的序列号整数.

in: 随机输入序列.

in_r: 随机输入序列的进制序列.

out_开头的则是输出结果.

解码算法流程与编码算法几乎一致, 但是把编码的输入和输出交换了一下, 同时进行了倒序处理, 并对解码序列与原始随机输入序列进行比较, 判断是否还原成功。

而验证步骤的关键伪代码还原如下:

/***** 省略前文 ******/
g_has_error = 0;
v9 = 0;
if ( check_error_in_x(__PAIR__(v7, v8)) )
{
if ( !g_has_error )
{
g_has_error = 0;
if ( check_error_in_x(__PAIR__(v7, v8) - 1) )
{
if ( g_has_error )
v9 = 1;
}
}
}
/***** 省略后文 ******/

要求对于输入的b能够使算法正确工作, 但是b - 1不能使算法正确工作。

解题思路

暴力枚举

此题的输入数据范围是介于 4K 到 4G 之间的一个整数, 可以考虑把核心算法单独摘出来整理重写, 然后进行暴力枚举。

但是枚举的难度在于, 原程序使用的随机输入序列长度为10000, 且使用多线程进行了约10000轮测试, 也就是说纯随机情况下, 如果数据量不够大, 很可能造成误判, 从而无法枚举出正确的序列号, 因此枚举的时间成本很高, 只是一个保底下策。

公式枚举

程序的算法是一个用于混合进制序列的编解码算法, 且需要一个控制参数来使算法正确工作. 而程序的验证机制是b正确且b - 1错误, 可以合理推测能够使算法正确工作的参数不止一个, 应该是一个连续区间, 且题目的正确答案是这个区间的左端点, 因此我们需要找出参数的取值规律, 从而快速求解答案。

翻一下逆向后的代码, 可以找到程序使用的进制集是{ 2, 4, 5, 6, 7, 8, 13 }, 且输入和输出使用了同一组进制。

.rdata:004031C8 _TEST_RADIX_LEN:
.rdata:004031C8 dw 7, 0
.rdata:004031CC ; int TEST_RADIX[]
.rdata:004031CC _TEST_RADIX dd 2, 4, 5, 6, 7, 8, 13 ; DATA XREF: do_error_check(x)+114r
.rdata:004031CC ; do_error_check(x)+15Er

猜想b的取值与进制组合有关, 因此可以从简单的入手, 暴力枚举小区间, 寻找规律。

分别设置以下几种方式去进行枚举, 可以得到正确的取值区间如下:

◆输入进制{ 2 }, 输出进制{ 2 }:[1, 5], [7, 18], [21, 39], [43, 68], [73, 105], ...

◆输入进制{ 2 }, 输出进制{ 3 }:[1, 7], [11, 26], [33, 57], [67, 100], [113, 155], ...

◆输入进制{ 3 }, 输出进制{ 3 }:[1, 10], [17, 38], [51, 84], [103, 148], ...

◆输入进制{ 2 }, 输出进制{ 2, 3 }:[1, 5], [7, 7], [11, 18], [21, 26], [33, 39], [43, 57], [67, 68], [73, 100], [113, 150], ...

◆输入进制{ 2, 3 }, 输出进制{ 2, 3 }:[1, 5], [7, 7], [17, 18], [21, 26], [33, 38], [51, 57], [67, 68], [73, 84], [113, 148], ...

观察一下可以发现, 对于混合进制的情况, 正确的取值区间是通过单个的输入输出进制的取值区间取交集得到的:

{ 2 }_{ 2, 3 } = { 2 }_{ 2 } & { 2 }_{ 3 }

{ 2, 3 }_{ 2, 3 } = { 2 }_{ 2, 3 } & { 3 }_{ 3 }

因此, 只要能找出单个的输入输出进制的取值区间规律就能解出题目.

继续观察寻找规律, 可以发现规律:

{ 2 }_{ 2 }:[4 * n^2 - (4 + 2) * n + 3, 4 * n^2 + n]

{ 2 }_{ 3 }:[6 * n^2 - (6 + 2) * n + 3, 6 * n^2 + n]

{ 3 }_{ 3 }:[9 * n^2 - (9 + 2) * n + 3, 9 * n^2 + n]

因此可以得到通项公式为:[r1 * r2 * n^2 - (r1 * r2 + 2) * n + 3, r1 * r2 * n^2 + n]

而题目使用了 7 种不同的进制, 且输入输出进制相同, 因此共需要枚举 21 种情况, 然后取交集最终得到题目里正确的取值范围, 并取左端点作为序列号。

这里需要注意的是, 取交集这个操作并不高效, 但是可以翻过来操作, 每次将错误取值区间筛去, 能够更快速的计算出正确答案, 这里贴一下核心计算代码。

void search_b(long long start, long long end)
{
long long p = 0;
long long n_s = 0;
long long n_e = 0;
long long b1 = 0;
long long b2 = 0;
long long b_count = end - start + 1;

bool* full_set = calloc((size_t)b_count, sizeof(bool));
if (!full_set)
return;

memset(full_set, 1, (size_t)b_count * sizeof(bool));

for (int i = 0; i < in_r_len; i++) {
for (int j = i; j < out_r_len; j++) {
p = in_r[i] * out_r[j];
n_s = left_floor(p, start);
n_e = right_ceil(p, end);

for (long long n = n_s; n <= n_e; n++) {
b1 = left(p, n);
b2 = right(p, n);

if (b1 < start)
b1 = start;
if (b2 > end)
b2 = end;

for (long long b_idx = b1 - start; b_idx <= b2 - start; b_idx++) {
full_set[b_idx] = 0;
}
}
}
}

for (long long b_s = 0; b_s < b_count; b_s++) {
if (full_set[b_s]) {
for (long long b_e = b_s; b_e < b_count; b_e++) {
if (!full_set[b_e]) {
printf("Valid: [%lld, %lld] Count: %lld\n", b_s + start, b_e - 1 + start, b_e - b_s);
b_s = b_e;
break;
}
}
}
}

if (full_set)
free(full_set);
return;
}

最终答案

最后算出来题目的进制组合下 100 亿范围内只有这些正确区间:

Valid: [1, 5] Count: 5
Valid: [7, 9] Count: 3
Valid: [1898766093, 1898766391] Count: 299
Valid: [79233213543, 79233230703] Count: 17161

题目要求范围在 4K 到 4G 的范围, 因此序列号为1898766093, 输入之后得到正确结果Accepted!。

赛题解析

本题解析由看雪大牛 GreatIchild 提供:
逆向部分没什么好说的,有个 check 算法,要在 1,000,000,000 到 1<<32 之间找一个数 k ,满足!check(k) && check(k - 1), check 函数大致如下:
def check(value, try_count):
buf1 = [0] * 10000
buf2 = [0] * 10000
buf3 = [0] * 20000
buf4 = [0] * 20000
for _ in range(try_count):
print(_, end=' \r')
v = [2, 4, 5, 6, 7, 8, 13]
for i in range(10000):
_v = v[rand() % len(v)]
buf1[i] = _v
if i == 0:
buf2[i] = rand() % (_v - 1) + 1
else:
buf2[i] = rand() % _v
for i in range(20000):
buf3[i] = v[rand() % len(v)]
i12 = 0
i34 = 0
tmpv = 0
while i12 < 10000 or tmpv > 0:
if i34 >= 20000:
# assert False, 1
return True
tmpv_bak = tmpv
if i12 >= 10000:
tmpv = tmpv // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
tmpv = buf1[i12] * tmpv + buf2[i12]
if tmpv_bak // buf3[i34] * tmpv >= value:
tmpv = tmpv_bak // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
i12 += 1
i12 = 10000 - 1
i34 -= 1
tmpv = 0
while i34 >= 0 or tmpv > 0:
if i12 < 0:
# assert False, 2
return True
tmpv_bak = tmpv
if i34 < 0:
tmpv = tmpv // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
# assert False, 3
return True
i12 -= 1
else:
tmpv = buf3[i34] * tmpv + buf4[i34]
if tmpv_bak // buf1[i12] * tmpv >= value:
tmpv = tmpv_bak // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
# assert False, 4
return True
i12 -= 1
else:
i34 -= 1
return False
程序使用了多线程,总共的 try_count 为 10000 。
直接看这算法完全不懂,于是来找规律。先固定 buf1 和 buf3 数组的值,当输入的 value 比较小的时候 (range(1, 512)) 发现返回值非常稳定,也就是 try_count 为 1 都能直接得到稳定结果,于是使用小 value 调整 buf1 buf3 的取值找规律,部分输出如下:
$ python3 ./script.py
[(28, True), (51, False), (107, True), (153, False), 238, True)]
$ python3./script.py
[(54, True), (103, False), (211, True)]
$ python3 ./script.py
[(28, True), (51, False), (54, True), (103, False), (107, True), (153, False), (211, True)]
上面的三次运行结果,是取 value 为range(1, 256), buf3 全为 13 , buf1 分别为 ① 全 2 ② 全 4 ③ 随机 2 和 4 这三种情况下的输出,输出的格式是返回值在某个值处发生了变化,变为了 True/False ,如第一次的输出含义是在 value = 28 时返回值开始为 True , value = 51 时返回值开始为 False ,以此类推。这些输出就得到了指定条件下能返回 True/False 的 value 值的区间。并且这个结果是非常稳定的,只需要一次就能得到这个正确的结果。
这三个综合起来就可以看到,第三次返回 False 的 value 区间就是第一次返回 False 的 value 区间与第二次的交集。
如果将 value 的范围改为range(1, 512),设置 buf1 全 2 , buf3 全 13 ,可以得到如下结果:
[(28, True), (51, False), (107, True), (153, False), 238, True), (307, False), (421, True)]
可以看到 True/False 的区间长度是二次递增的(相邻 True 区间或者相邻 False 区间的长度差是一个等差数列),总之就是我们可以通过前几个区间值递推到我们想要的区间的 True/False 分布。
所以我们只要找到某组 buf1 和 buf3 的固定取值下 value 在range(1, 256)里的 True/False 分布(必须是稳定的),我们就能找到这些取值下 value 在 1,000,000,000 到 1<<32 之间的 True/False 分布,再结合第一条规律,不同 buf1 和 buf3 的取值下得到的返回 False 的取值区间的交就一定包含目标区间,这样就能大大缩小需要暴破的空间。
后面测试发现, buf1 与 buf3 的固定取值存在倍数关系时得到的结果不稳定,所以排除这一部分数据。最后共有 18 组组合,将暴破区间从 3294967296 减少到 87551 。
#!/usr/bin/env python3

'''
seed = 0
def rand():
global seed
seed += 1
return seed
'''

def rand(): # simulate rand (may be any random function)
pass

def check(value, try_count): # check
pass

def check_1(value, buf1_v, buf3_v):
print(value, end=' \r')
buf1 = [buf1_v] * 10000
buf2 = [rand() % (buf1_v - 1) + 1]
for i in range(1, 10000):
buf2.append(rand() % buf1_v)
buf3 = [buf3_v] * 20000
buf4 = [0] * 20000
i12 = 0
i34 = 0
tmpv = 0
while i12 < 10000 or tmpv > 0:
if i34 >= 20000:
return True
tmpv_bak = tmpv
if i12 >= 10000:
tmpv = tmpv // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
tmpv = buf1[i12] * tmpv + buf2[i12]
if tmpv_bak // buf3[i34] * tmpv >= value:
tmpv = tmpv_bak // buf3[i34]
buf4[i34] = tmpv_bak % buf3[i34]
i34 += 1
else:
i12 += 1
i12 = 10000 - 1
i34 -= 1
tmpv = 0
while i34 >= 0 or tmpv > 0:
if i12 < 0:
return True
tmpv_bak = tmpv
if i34 < 0:
tmpv = tmpv // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
return True
i12 -= 1
else:
tmpv = buf3[i34] * tmpv + buf4[i34]
if tmpv_bak // buf1[i12] * tmpv >= value:
tmpv = tmpv_bak // buf1[i12]
if tmpv_bak % buf1[i12] != buf2[i12]:
return True
i12 -= 1
else:
i34 -= 1
return False

try_count = 150

'''
low = 1000000000
v_low = check(low, try_count)
print(low, v_low)

high = 0x100000000
v_high = check(high, try_count)
print(high, v_high)

while low < high:
mid = (low + high) // 2
v_mid = check(mid, try_count)
print(mid, v_mid)
if v_mid == v_low:
low = mid + 1
v_low = check(low, try_count)
print(low, v_low)
else:
high = mid - 1
v_high = check(high, try_count)
print(high, v_high)
'''

def interval_and(l1, l2):
l = []
i1 = 0
i2 = 0
while i1 < len(l1) and i2 < len(l2):
l1a, l1b = l1[i1]
l2a, l2b = l2[i2]
if l1a >= l2b:
i2 += 1
continue
elif l2a >= l1b:
i1 += 1
elif l1b >= l2b:
l.append((max(l1a, l2a), l2b))
i2 += 1
if l1b == l2b:
i1 += 1
else:
l.append((max(l1a, l2a), l1b))
i1 += 1
return l

def get_f_intervals(t, f, tdiv, fdiv, pub_div):
assert t < f
t = t + tdiv
tdiv += pub_div
assert t > f
while t < 1000000000:
f += fdiv
fdiv += pub_div
t += tdiv
tdiv += pub_div
fl = []
while f < 0x100000000:
fl.append((f, t))
f += fdiv
fdiv += pub_div
t += tdiv
tdiv += pub_div
return fl

def number_count(l):
s = 0
for a, b in l:
s += b - a
return s

'''
last_r = False
a = []
for i in range(1, 1024):
r = check_1(i, 2, 13)
if last_r != r:
a.append((i, r))
if len(a) >= 8: break
last_r = r
# print(a)

print(a)
print(a[2][0] - a[0][0], a[4][0] - a[2][0], a[6][0] - a[4][0])

x=a[0][0]
y=a[2][0]
z=a[4][0]
x1=a[1][0]
y1=a[3][0]
print(x,x1,y-x,y1-x1,(z-y)-(y-x))
'''

s='''
28 51 79 102 52
54 103 157 206 104
67 129 196 258 130
80 155 235 310 156
93 181 274 362 182
106 207 313 414 208

16 27 43 54 28
30 55 85 110 56
37 69 106 138 70
44 83 127 166 84
58 111 169 222 112

12 19 31 38 20
22 39 61 78 40
32 59 91 118 60
42 79 121 158 80

14 23 37 46 24
26 47 73 94 48
50 95 145 190 96
'''

fl = [(1000000000, 0x100000000)]
n = number_count(fl)

for i in s.strip().split('\n'):
if not i.strip(): continue
fl = interval_and(fl, get_f_intervals(*(int(j) for j in i.split(' '))))
last_n = n
n = number_count(fl)
print('{} -> {} (-{}%)'.format(last_n, n, 100 * (last_n - n) / last_n))

for i in fl:
print(i, i[1] - i[0])

筛选后得到的区间:
(1124320915, 1124327425) 6510
(1898762303, 1898787472) 25169
(2133213325, 2133231523) 18198
(2793543721, 2793581395) 37674
这个空间就可以开始暴了,暴的过程中发现第 2 个区间会有一些误报,而其他都没有,猜测是目标区间就在第二个区间里,区间内其他值离目标值比较近,误报的概率就高了,所以直接写程序暴这个区间内的值:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <assert.h>
#include <sys/types.h>
#include <unistd.h>

#define ullong unsigned long long

int check(ullong value, int try_count) {
int buf1[10000];
int buf2[10000];
int buf3[20000];
int buf4[20000];
// printf("%d, %d, %d, %d\n", buf1[0], buf2[0], buf3[0], buf4[0]);
unsigned int v[] = {2, 4, 5, 6, 7, 8, 13};
for (int _ = 0; _ < try_count; _++) {
for (int i = 0; i < 10000; i++) {
int _v = v[rand() % 7];
buf1[i] = _v;
if (i) {
buf2[i] = rand() % _v;
} else {
buf2[i] = rand() % (_v - 1) + 1;
}
}

for (int i = 0; i < 20000; i++) {
buf3[i] = v[rand() % 7];
}
int i12 = 0;
int i34 = 0;
ullong tmpv = 0;
while (i12 < 10000 || tmpv > 0) {
if (i34 >= 20000) {
assert(0 || "1");
return 1;
}
ullong tmpv_bak = tmpv;
if (i12 >= 10000) {
tmpv = tmpv / buf3[i34];
buf4[i34] = tmpv_bak % buf3[i34];
i34 += 1;
} else {
tmpv = buf1[i12] * tmpv + buf2[i12];
if (tmpv_bak / buf3[i34] * tmpv >= value) {
tmpv = tmpv_bak / buf3[i34];
buf4[i34] = tmpv_bak % buf3[i34];
i34 += 1;
} else {
i12 += 1;
}
}
}
i12 = 10000 - 1;
i34 -= 1;
tmpv = 0;
while (i34 >= 0 || tmpv > 0) {
if (i12 < 0) {
assert(0 || "2");
return 1;
}
ullong tmpv_bak = tmpv;
if (i34 < 0) {
tmpv = tmpv / buf1[i12];
if (tmpv_bak % buf1[i12] != buf2[i12]) {
return 1;
}
i12 -= 1;
} else {
tmpv = buf3[i34] * tmpv + buf4[i34];
if (tmpv_bak / buf1[i12] * tmpv >= value) {
tmpv = tmpv_bak / buf1[i12];
if (tmpv_bak % buf1[i12] != buf2[i12]) {
return 1;
}
i12 -= 1;
} else {
i34 -= 1;
}
}
}
}
return 0;
}

int main() {
setbuf(stdout, NULL);

int try_count = 100;
srand(time(NULL));

#define PROCESS_COUNT 16
#define INIT_VALUE (1898762303l)
#define FINI_VALUE (1898787472l)
#define TASK_COUNT ((FINI_VALUE - INIT_VALUE) / PROCESS_COUNT)

#define LOG_TOTAL (100)
#define COUNT_TO_LOG (TASK_COUNT / LOG_TOTAL)

for (int j = 0; j < PROCESS_COUNT; j++) {
if (!fork()) { // child
int logged_count = 0;
int counting = COUNT_TO_LOG;
printf("process %d started (0x%lx - 0x%lx).\n", j, INIT_VALUE + j * TASK_COUNT, INIT_VALUE + j * TASK_COUNT + TASK_COUNT);
for (ullong i = INIT_VALUE + j * TASK_COUNT; i < INIT_VALUE + j * TASK_COUNT + TASK_COUNT; i++) {
if (!check(i, try_count) && !check(i, 10000)) {
printf("found: %lld\n", i);
} else {
// printf("\r%lld", i);
}
counting--;
if (counting <= 0) {
counting = COUNT_TO_LOG;
logged_count += 1;
printf("process %d: %d / %d\n", j, logged_count, LOG_TOTAL);
}
}
printf("process %d done.\n", j);
exit(0);
}
}

getchar();
return 0;
}

跑了可能有半小时,输出里找了下很容易看到有一段连续好几百个值,这就是目标区间。当然里面还有一些误报的值, 2 万多个数误报了 20 多个,但是显然这些值是没法重复稳定通过的,只有这个区间里的值能稳定过!check。最后回到问题,满足!check(k) && check(k - 1)的值就是这个区间里的最小值 1898766093 。

今日中午12:00
第十二题《深入内核》已开赛!
在这个充满变数的赛场上,没有人能够预料到最终的结局。有时,优势的领先可能只是一时的,一瞬间的失误就足以颠覆一切。而那些一直默默努力、不断突破自我的人,往往会在最后关头迎头赶上,成为最耀眼的存在。
谁能保持领先优势?谁能迎头赶上?谁又能突出重围成为黑马?

球分享

球点赞

球在看

点击阅读原文进入比赛


文章来源: https://mp.weixin.qq.com/s?__biz=MjM5NTc2MDYxMw==&mid=2458520790&idx=1&sn=c82a730ba8566df4f220c849d7ed2087&chksm=b18d3c5c86fab54a7e5f0947d3db3bc1f39643290c8eef89626d64705ea51e8fcb1618d0fba6&scene=58&subscene=0#rd
如有侵权请联系:admin#unsafe.sh