小说网站排名人气,网络营销是不是网络销售,安徽建筑人才网,网站设计论文答辩问题一.题目描述 二.输入描述 三.输出描述 四.问题分析
几个两两互质的数#xff0c;最大公约数是1#xff0c;最小公倍数是他们的乘积。 两个互质的数a和b最小不能表示的数就是#xff08;a-1#xff09;#xff08;b-1#xff09;-1#xff0c;即#xff0c;两个互质的数…一.题目描述 二.输入描述 三.输出描述 四.问题分析
几个两两互质的数最大公约数是1最小公倍数是他们的乘积。 两个互质的数a和b最小不能表示的数就是a-1b-1-1即两个互质的数ab可以表示a-1b-1之后的所有数字。
此定理用于确定数字的上界。100-1*99-1-110000 如果两个数不互质则只要不是这两个数最大公约数的倍数都凑不出来。
//包子凑数
#include iostream
#include algorithmusing namespace std;const int MAX1e5;//数字上限
bool d[MAX]{0};//表示是否能够凑出包子数为i的情况
int baozi[110],ans0;int gcd(int a,int b){if(ab)swap(a,b);while(b){int xa%b;ab;bx;}return a;
}int main(int argc, const char * argv[]) {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,g0;cinn;for(int i1;in;i){cinbaozi[i];if(i1)gbaozi[i];elseggcd(g,baozi[i]);}if(g!1){coutINF\n;}else{d[0]1;for(int i1;in;i){for(int jbaozi[i];jMAX;j){d[j]d[j]|d[j-baozi[i]];}}for(int i1;iMAX;i){if(d[i]0)ans;}}coutans;return 0;
}
