打表找规律（Python）

思路：非常经典的打表找规律题目，其背后的本质是：1.裴蜀定理：对于整数a和b，方程ax + by = n有整数解，当且仅当 gcd(a,b)∣n，也就是gcd能够去整除n。2.弗罗贝尼乌斯硬币结论：对于互质的正整数a和b，最大的不能表示为ax + by（x,y ≥ 0）的数是：ab − a − b。

因此，我们打个表可以发现如下规律：1.索引0~16，也就是前17个数没有规律性，直接收集到ans数组中回答即可；2.从索引17开始，每8个为一组，形成了的规律，那我们就在奇数的时候输出-1，偶数的时候就先用当前数n - 前17个舍去的数，再// 8 + 起始值3，就能得到表示的答案了

代码：

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def solve():
    n = II()

    # 打表
    # for i in range(n):
    #     ans = inf
    #     def dfs(i, cnt):
    #         nonlocal ans
    #         if i < 0:
    #             return
    #         if i == 0:
    #             ans = fmin(ans, cnt)
    #             return
    #         dfs(i - 6, cnt + 1)
    #         dfs(i - 8, cnt + 1)
    #     dfs(i, 0)
    #     print(i, ans if ans < inf else -1)

    ans = [0, -1, -1, -1, -1, -1, 1, -1, 1, -1, -1, -1, 2, -1, 2, -1, 2]
    if n <= 16:
        print(ans[n])
    else:
        if n & 1:
            print(-1)
        else:
            print((n - 17) // 8 + 3)

t = 1
# t = II()
for _ in range(t):
    solve()