若给出参数
a
,
b
,
c
a,b,c
a,b,c,不定方程
a
x
+
b
y
=
c
ax+by=c
ax+by=c有解的充要条件是
g
c
d
(
a
,
b
)
∣
c
gcd(a,b)|c
gcd(a,b)∣c
g c d ( a , b ) gcd(a,b) gcd(a,b)显然是 a x ax ax的一个因子,也是 b y by by的一个因子,所以 a x + b y ax+by ax+by的含义为 g c d ( a , b ) gcd(a,b) gcd(a,b)的两个倍数相加,结果一定还是 g c d ( a , b ) gcd(a,b) gcd(a,b)的倍数,所以只需要 g c d ( a , b ) ∣ c gcd(a,b)|c gcd(a,b)∣c,方程就有解
同样的原理,可以扩展至任意个数的参数:
给出
n
n
n个参数
a
i
a_{i}
ai与
c
c
c,使方程
∑
i
=
1
n
a
i
x
i
=
c
\sum_{i=1}^{n}a_{i}x_{i}=c
i=1∑naixi=c
有解的充要条件是
g
c
d
(
a
1
,
a
2
,
.
.
.
,
a
n
)
∣
c
gcd(a_{1},a_{2},...,a_{n})|c
gcd(a1,a2,...,an)∣c
给出
n
n
n个参数
a
i
a_{i}
ai,求另一个整数序列
x
i
x_{i}
xi,使得
S
=
∑
i
=
1
n
a
i
x
i
S=\sum_{i=1}^{n}a_{i}x_{i}
S=i=1∑naixi
满足
S
>
0
S>0
S>0,且
S
S
S最小
显然右式是一个不定方程,那么 S S S要存在取值就只可能是 g c d ( a 1 , a 2 , . . . , a n ) gcd(a_{1},a_{2},...,a_{n}) gcd(a1,a2,...,an),这个就是答案了。不过 a i a_{i} ai可能是负的,只需要取负 a i a_{i} ai在计算就可以保证是正的了
// #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
using ll=long long;
using ull=unsigned long long;
const int N=2e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=1e9+9;
int main()
{
#ifdef stdjudge
freopen("in.txt","r",stdin);
#endif
int ans,n; cin>>n>>ans;
if(ans<0) ans=-ans;
while(--n)
{
int x; cin>>x;
if(x<0) x=-x;
ans=__gcd(ans,x);
}
cout<<ans;
return 0;
}