---

文章目录

• 买不到的数目
• 错误票据

---

一、买不到的数目OJ链接

本题思路:引理：给定a，b，若d=gcd(a,b)>1 ,则一定不能凑出最大数。结论：如果 a,b均是正整数且互质，那么由 ax+by,x≥0,y≥0 不能凑出的最大数是 ab−a−b。

证明:首先证明 ab−a−b不能被 ax+bx,x≥0,y≥0表示出。
反证法:假设 ab−a−b=ax+by，那么 ab=a(x+1)+b(y+1)，由于 a|ab,a|a(x+1)，所以 a|b(y+1)，由于 a,b 互质，所以 a|(y+1)，由于 y≥0，所以 a<=y+1，所以 b(y+1)≥ab。同理可得 a(x+1)≥ab，所以 a(x+1)+b(y+1)≥2ab>ab，矛盾。证明 ab−a−b+d,d>0一定可以表示成 ax+by,x,y≥0 的形式

#include <bits/stdc++.h>int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int a,b;std::cin>>a>>b;int d=std::lcm(a,b);std::cout<<d-a-b<<std::endl;return 0;
}

二、错误票据OJ链接

本题思路:本题通过排序的方式来枚举即可。

#include <bits/stdc++.h>constexpr int N=10010;int n,m;
int a[N];int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cin>>n;std::string line;//将第一行的回车读入std::getline(std::cin,line);while(n--){std::getline(std::cin,line);//stringstream 默认是以空格来分割字符串的std::stringstream ssin(line);while(ssin>>a[m]){m++;}}//排序std::sort(a,a+m);int d=-1,c=-1;//d是找出重复的,c是找出缺失的//从前往后枚举即可for(int i=0;i<m-1;i++){if(a[i]==a[i+1]) d=a[i];else if(a[i+1]==a[i]+2) c=a[i]+1;}std::cout<<c<<" "<<d<<std::endl;return 0;
}