2017蓝桥杯C/C++A组省赛包子凑数(辗转相除法和完全背包)

时间:2022-03-13 06:12:20

答案:

#include<bits/stdc++.h>
using namespace std;

bool judge(int x,int y)
{
int t;
while(y>0)
{
t=x%y;
x=y;
y=t;
}
if(x==1)
return true;
return false;
}

int a[110],n;
bool dp[10010];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
int flag=0;
for(int i=0;i<n;i++)
{
for(int j=1;j<=n;j++)
{
if(judge(a[i],a[j]))
{
flag=1;
break;
}
}
if(flag==1)
break;
}
if(flag!=1)
{
printf("INF\n");
return 0;
}
dp[0]=1;
for(int i=0;i<n;i++)
{
for(int j=0;j+a[i]<10000;j++)
if(dp[j])
dp[j+a[i]]=1;
}
int ans=0;
for(int i=0;i<10000;i++)
{
if(dp[i]!=1)
ans++;
}
printf("%d\n",ans);
return 0;
}


预备知识

辗转相除法

(原理:假设有两个数x和y,存在一个最大公约数z=(x,y),即x和y都有公因数z,
那么x一定能被z整除,y也一定能被z整除,所以x和y的线性组合mx±ny也一定能被z整除。(m和n可取任意整数)
对于辗转相除法来说,思路就是:若x>y,设x/y=n余c,则x能表示成x=ny+c的形式,将ny移到左边就是x-ny=c,由于一般形式的mx±ny能被z整除,所以等号左边的x-ny(作为mx±ny的一个特例)就能被z整除,即x除y的余数c也能被z整除。

(以下是挑战程序设计竞赛的内容)

1.求最大公约数

例题:线段上格点的个数

。。。。。

3.扩展欧几里得算法

对辗转相除法做一下扩展

例题:双六

这个问题用数学语言表述就是“求整数X和Y使得ax+bt=1”.可以发现,如果gcd(a,b)!=1,则无解,反之,如果gcd(a,b)=1,就可以通过扩展原来的辗转相除法来求解。事实上,一定存在整数对(x,y)使得ax+by=gcd(a,b),并可以用同样的算法求得

int extgcd(int a,int b,int& x,int& y)
{
int d=a;
if(b!=0)
{
d=extgcd(b,a%b,y,x);
y=y-(a/b)*x;
}
else
{
x=1;
y=0;
}
return d;
}