a811 - 2. 迷路小鴨
題目描述
題目要求計算一組數字中，相鄰數字差值的最大公因數。給定一個整數 c，代表數字的個數，接著輸入 c 個整數。輸出這些數字排序後，相鄰數字差值的最大公因數。
解題思路
首先，對輸入的數字進行排序。然後，計算排序後相鄰數字之間的差值。接著，對這些差值進行迭代計算最大公因數 (GCD)。最終，輸出所有差值計算出的最大公因數。使用貪心策略，逐步計算差值並更新最大公因數。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是輸入數字的個數。排序操作佔據主導地位。GCD 計算的複雜度較小，可以忽略。
- 空間複雜度: O(n)，用於儲存輸入數字和差值。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <algorithm>
using namespace std;
inline long long int gcd(long long int a,long long int b){
if (b)
while((a %= b) && (b %= a));
return a+b;
}
inline long long int read(){
long long int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(long long int x) {
long long int stk[12],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
long long int c(read());
while(c=read()){
long long int k[c];
for(int i(0);i<c;++i)
k[i]=read();
sort(k,k+c);
--c;
for(int i(0);i<c;++i){
k[i]=k[i+1]-k[i];
if(i)
k[i]=gcd(k[i],k[i-1]);
}
write(k[c-1]);
putchar_unlocked('\n');
}
}