即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

bzoj1441Min 裴蜀定理

编程语言 qq_35866453 13℃ 0评论

一开始以为是什么构造题目,后来才发现是裴蜀定理。。


裴蜀定理:若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。


也就是说,忽略符号,gcd(a,b)就是ax+by所能表示的最小正整数


对所有的数求gcd即可

#include
#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e5+5;
int n,m,x,ans;

int a[N];
int gcd(int a,int b)
{
    if (!b) return a;
    else return gcd(b,a%b);
}
int main()
{
    scanf("%d",&n);
    scanf("%d",&ans);
    ans=abs(ans);
    fo(i,1,n-1)
    {
        scanf("%d",&x);
        x=abs(x);
        ans=gcd(ans,x);
    }
    printf("%d\n",ans);
}

转载请注明:CodingBlog » bzoj1441Min 裴蜀定理

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情