看雪2023 KCTF年度赛 | 第11题·步步逼近-设计思路及解析

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

$ 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)]

[(28, True), (51, False), (107, True), (153, False), 238, True), (307, False), (421, True)]

#!/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

#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, %dn", 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: %lldn", i);
                } else {
                    // printf("r%lld", i);
                }
                counting--;
                if (counting <= 0) {
                    counting = COUNT_TO_LOG;
                    logged_count += 1;
                    printf("process %d: %d / %dn", j, logged_count, LOG_TOTAL);
                }
            }
            printf("process %d done.n", j);
            exit(0);
        }
    }

    getchar();
    return 0;
}