当前位置:网站首页>[蓝桥杯2017初赛]包子凑数
[蓝桥杯2017初赛]包子凑数
2022-07-06 09:14:00 【%xiao Q】
题目
题目描述
小明几乎每天早晨都会在一家包子铺吃早餐。这家包子铺有N种蒸笼,其中第i种蒸笼恰好能放Ai个包子
每种蒸笼都有非常多笼,可以认为是无限笼。
每当有顾客想买X个包子,卖包子的大叔就会选出若干笼包子来,使得这若干笼中恰好一共有X个包子。
比如一共有3种蒸笼,分别能放3、4和5个包子。当顾客想买11个包子时,大叔就会选2笼3个的再加1笼5个的(也可能选出1笼3个的再加2笼4个的)。
当然有时包子大叔无论如何也凑不出顾客想买的数量。
比如一共有3种蒸笼,分别能放4、5和6个包子。而顾客想买7个包子时,大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入格式
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)
输出格式
输出一行包含一个整数代表答案。如果凑不出的数目有无限多个,输出INF。
输入样例 复制
2
4
5
输出样例 复制
6
数据范围与提示
对于样例,凑不出的数目包括:1, 2, 3, 6, 7, 11。
分析:
这题得知道一个定理,即欧几里徳定理:对于不完全为0的整数a,b那么一定存在整数x,y使得gcd(x,y) = a * x + b * y。
所以我们可以假设a * x + b * y = d,要使该方程有解,那么d % gcd(a, b) = 0是必然的,如果gcd(a,b) = 1,那么d就能整除任何数,也就说a,b这2个数可以凑除任何数(但是里面不能有负数,所以存在一些数是凑不出来的),反之不能。
所以第一步我们得找出这些数的最大公约数,如果gcd = 1,那么在判断里面有多少个数凑不出来,如果gcd != 1,那么一定会有无数种数凑不出来,直接输出INF。
参考代码:
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++)
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;
const int N = 10010, M = 110;
int f[N];
int a[N];
int main()
{
int n;
cin >> n;
int g = 0;
rep(i, 1, n)
{
cin >> a[i];
g = __gcd(g, a[i]);
}
if(g != 1)
{
puts("INF");
return 0;
}
rep(i, 1, n) f[a[i]] = 1;
rep(i, 1, n)
for(int j = 0; j + a[i]<= 10000; j++) // 这里到10000有点玄学(数学,不会呀)
{
if(f[j]) f[j + a[i]] = 1;
}
int ans = 0;
rep(i, 1, 10000)
if(!f[i]) ans++;
cout << ans << endl;
return 0;
}
边栏推荐
- 虚拟机Ping通主机,主机Ping不通虚拟机
- [recommended by bloggers] C MVC list realizes the function of adding, deleting, modifying, checking, importing and exporting curves (with source code)
- AcWing 1294.樱花 题解
- QT creator design user interface
- Ubuntu 20.04 安装 MySQL
- MySQL主从复制、读写分离
- Image recognition - pyteseract TesseractNotFoundError: tesseract is not installed or it‘s not in your path
- Postman uses scripts to modify the values of environment variables
- 02-项目实战之后台员工信息管理
- LeetCode #461 汉明距离
猜你喜欢
Other new features of mysql18-mysql8
软件测试与质量学习笔记3--白盒测试
QT creator support platform
Postman uses scripts to modify the values of environment variables
连接MySQL数据库出现错误:2059 - authentication plugin ‘caching_sha2_password‘的解决方法
解决安装Failed building wheel for pillow
02-项目实战之后台员工信息管理
基于apache-jena的知识问答
学习问题1:127.0.0.1拒绝了我们的访问
QT creator runs the Valgrind tool on external applications
随机推荐
[recommended by bloggers] asp Net WebService background data API JSON (with source code)
[recommended by bloggers] C MVC list realizes the function of adding, deleting, modifying, checking, importing and exporting curves (with source code)
The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
SSM整合笔记通俗易懂版
[recommended by bloggers] C # generate a good-looking QR code (with source code)
How to configure flymcu (STM32 serial port download software) is shown in super detail
记某公司面试算法题:查找一个有序数组某个数字出现的次数
Antlr4 uses keywords as identifiers
JDBC原理
Windows cannot start the MySQL service (located on the local computer) error 1067 the process terminated unexpectedly
Request object and response object analysis
Why can't STM32 download the program
Image recognition - pyteseract TesseractNotFoundError: tesseract is not installed or it‘s not in your path
Ansible实战系列一 _ 入门
Record a problem of raspberry pie DNS resolution failure
windows下同时安装mysql5.5和mysql8.0
Are you monitored by the company for sending resumes and logging in to job search websites? Deeply convinced that the product of "behavior awareness system ba" has not been retrieved on the official w
Learning question 1:127.0.0.1 refused our visit
记一次某公司面试题:合并有序数组
LeetCode #461 汉明距离