数学法——使用O(1)复杂度解决问题

原题链接：472.百钱买百鸡

学C++的第N天

2024-06-28 21:34:12

发布于：上海

91阅读

0回复

0点赞

我们令公鸡有 $i$ 只,母鸡有 $j$ 只,小鸡有 $k$ 只，题目的本质即求方程组： $\begin{cases}i+j+k=n\\ 5i+3j+\cfrac{k}{3}=n\end{cases}$ 的整数解的个数，应用初中数学知识可以求出这个方程的正整数解 $\begin{cases}i=4m+3n\\j=-7m-5n\\k=3m+3n\\\end{cases}(m\in Z)$ ，只要确定 $m$ 的范围即可得到其正整数解的个数了.
事实上，题目有额外约束 $0\leq i,j,k\leq n$ ,因此我们不难列出不等式组 $\begin{cases}0\leq 4m+3n\leq n\ \ \ \ (1)\\0\leq -7m-5n\leq n\ (2)\\0\leq 3m+3n \leq n\ \ \ \ (3)\\\end{cases}$ ,可以得到：

$m\in[-\cfrac{3}{4}n,-\cfrac{1}{2}n]\cap[-\cfrac{6}7{n,-\cfrac{5}{7}n}]\cap[-n,-\cfrac{2}{3}n],即m\in[-\cfrac{3}{4}n,-\cfrac{5}{7}n]$

只需要求区间 $[-\cfrac{3}{4}n,-\cfrac{5}{7}n]$ 内的整数即可!
这是一个可行的代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n=0;
    cin>>n;
    float a = ceil(-(3.0/4.0)*n);
    float b = floor(-(5.0/7.0)*n);
    cout<<abs(b-a)+1;
}