CF1912J Joy of Pokémon Observation记录

发布时间 2023-12-20 00:30:27作者: cccpchenpi

题目链接:https://codeforces.com/contest/1912/attachments/download/23419/icpc-nerc-2023-statements.pdf

题意简述

求方程 \(\sum \limits_{i =1}^{s} l_i x_i = t\) 的非负整数解的个数。

不多于 \(1024\) 组用例,\(t \le 10^9, s \le 3, l_i \le 16\)

题解(官解)

赛时我光想着怎么求一般方程的解的个数了,没找到什么有用的结果,结果 \(l_i \le 16\) 的条件很重要。

\(s = 1\) 时很显然,若 \(t \equiv 0 \mod l_1\),答案为 \(1\),否则为 \(0\)

\(s = 2\) 时,即求 \(a \cdot i_a + b \cdot i_b = l\) 解的个数。令 \(i_a = k_a \cdot b +j_a\),枚举 \(j_a\)