牛客挑戰(zhàn)賽47 A 一道GCD問題

思路參考牛客上的題解：
根據多維的更相減損術得gcd(x,y,z)=gcd(x,y?x,z?y)得
gcd(a1+k,a2+k,a3+k…,an+k)=gcd(a1+k,a2-a1,a3-a2…)gcd(a1+k,a2+k,a3+k…,an+k)=gcd(a1+k,a2?a1,a3?a2…)
我們很容易可以求得等式右邊的值為g我們很容易可以求得等式右邊的值為g
那么對于最小得k就是(g-a1%g)%g 注意要排序；
參考鏈接：來自ID：7QQQQQQQ的評論

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se second #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define ac cout<<ans<<"\n" using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=1e9+7; const ll N =1e6+10; const double eps = 1e-4; //const double pi=acos(-1); int n; ll a[N]; void sovle(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);ll now=0;for(int i=2;i<=n;i++){now=__gcd(now,a[i]-a[i-1]);}ll k=(now-a[1]%now)%now;cout<<now<<' '<<k<<endl; } int main() {iosint t=1;// cin>>t;while(t--){sovle();}return 0; }

總結

以上是生活随笔為你收集整理的牛客挑战赛47 A 一道GCD问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。