題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的數組 $a$，再給出一個長度為 $m$ 的數組 $b$，現在要求輸出，當 $j=1,2,...,m$ 時的答案：$gcd(a_1+b_j,a_2+b_j,...,a_n+b_j)$

題目分析：一個公式 $gcd(x,y)=gcd(x,x?y)$ $from$ 百度百科

然后對于 $b_j$ 推一下公式：

$$\begin{array}{rl}& gcd(a_1+b_j,a_2+b_j)\\ & =gcd(a_1+b_j,a_2+b_j)\\ & =gcd(a_1+b_j,(a_1+b_j)?(a_2+b_j))\\ & =gcd(a_1+b_j,a_1?a_2)\end{array}$$

從后向前遞推：

$$\begin{array}{rl}& gcd(a_1+b_j,a_2+b_j,...,a_{n?1}+b_j,a_n+b_j)\\ & =gcd(a_1+b_j,a_2+b_j,...,a_{n?1}+b_j,a_{n?1}?a_n)\\ & =gcd(a_1+b_j,a_1?a_2,...,a_{n?2}?a_{n?1},a_{n?1}?a_n)\end{array}$$

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;LL a[N],b[N];int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);LL gcd=0;for(int i=1;i<=n;i++){scanf("%I64d",a+i);if(i!=1)gcd=__gcd(gcd,abs(a[i]-a[i-1]));}for(int i=1;i<=m;i++)scanf("%I64d",b+i);for(int i=1;i<=m;i++)printf("%I64d ",__gcd(b[i]+a[1],gcd));puts("");return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1459C Row GCD(数论+推公式)的全部內容，希望文章能夠幫你解決所遇到的問題。

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