当前位置:网站首页>[Blue Bridge Cup 2017 preliminary] buns make up
[Blue Bridge Cup 2017 preliminary] buns make up
2022-07-06 11:25:00 【%xiao Q】
subject
Title Description
Xiao Ming has breakfast in a bun shop almost every morning . This bun shop has N Grow steamer , Among them the first i The kind of steamer can put Ai A steamed bun
Each kind of steamer has a lot of steamers , It can be thought of as an infinite cage .
Whenever a customer wants to buy X A steamed bun , Uncle will choose some steamed buns , So that these cages happen to have X A steamed bun .
Let's say there are 3 Grow steamer , You can put 3、4 and 5 A steamed bun . When customers want to buy 11 A bun , Uncle will choose 2 Cage 3 One more 1 Cage 5 One of the ( It is also possible to elect 1 Cage 3 One more 2 Cage 4 One of the ).
Of course, sometimes uncle baozi can't figure out the quantity customers want to buy .
Let's say there are 3 Grow steamer , You can put 4、5 and 6 A steamed bun . And customers want to buy 7 A bun , Uncle can't make it out .
Xiao Ming wants to know how many kinds of numbers can't be found by Uncle baozi .
Input format
The first line contains an integer N.(1 <= N <= 100)
following N Each line contains an integer Ai.(1 <= Ai <= 100)
Output format
The output line contains an integer to represent the answer . If you can't figure out an infinite number , Output INF.
sample input Copy
2
4
5
sample output Copy
6
Data range and tips
For example , The uncountable number includes :1, 2, 3, 6, 7, 11.
analysis :
This problem needs to know a theorem , Euclidean theorem : For not completely 0 The integer of a,b So there must be integers x,y bring gcd(x,y) = a * x + b * y.
So we can assume that a * x + b * y = d, To make the equation solvable , that d % gcd(a, b) = 0 It is inevitable , If gcd(a,b) = 1, that d Can divide any number , That is to say a,b this 2 Any number can be divided by numbers ( But there can't be negative numbers in it , So there are some numbers that cannot be summed up ), On the contrary, we can't .
So the first step is to find the greatest common divisor of these numbers , If gcd = 1, Then how many numbers can't be summed up in the judgment , If gcd != 1, Then there must be countless kinds of numbers that can't be summed up , Direct output INF.
Reference code :
#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++) // Here to 10000 It's a little metaphysical ( mathematics , No )
{
if(f[j]) f[j + a[i]] = 1;
}
int ans = 0;
rep(i, 1, 10000)
if(!f[i]) ans++;
cout << ans << endl;
return 0;
}
边栏推荐
猜你喜欢
Valentine's Day flirting with girls to force a small way, one can learn
double转int精度丢失问题
[蓝桥杯2017初赛]方格分割
Vs2019 first MFC Application
Did you forget to register or load this tag 报错解决方法
保姆级出题教程
Detailed reading of stereo r-cnn paper -- Experiment: detailed explanation and result analysis
PyCharm中无法调用numpy,报错ModuleNotFoundError: No module named ‘numpy‘
Double to int precision loss
Why can't I use the @test annotation after introducing JUnit
随机推荐
Rhcsa certification exam exercise (configured on the first host)
vs2019 桌面程序快速入门
double转int精度丢失问题
In the era of DFI dividends, can TGP become a new benchmark for future DFI?
软件测试-面试题分享
Use dapr to shorten software development cycle and improve production efficiency
Did you forget to register or load this tag
数数字游戏
Unable to call numpy in pycharm, with an error modulenotfounderror: no module named 'numpy‘
How to set up voice recognition on the computer with shortcut keys
Detailed reading of stereo r-cnn paper -- Experiment: detailed explanation and result analysis
Double to int precision loss
AcWing 179. Factorial decomposition problem solution
Django运行报错:Error loading MySQLdb module解决方法
Remember a company interview question: merge ordered arrays
數據庫高級學習筆記--SQL語句
LeetCode #461 汉明距离
Face recognition_ recognition
What does BSP mean
Codeforces Round #753 (Div. 3)