【gcd】CF6691div1 A. Row GCD

忘是亡心i 2024-03-22 13:27 60阅读 0赞

[Problem - A - Codeforces][]

题意：

![7380f034bb90485e9e0d58dcfe3f9919.png][]

思路：

辗转相除法搞一搞就行

![4a1dc6c1e69f42caad889be608d68cf4.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxv=1e6+10; 
    const int mod=1e9+7;
    
    vector<int> v;
    
    int N,M;
    int a[mxn],b[mxn];
    
    void solve(){
    	v.clear(); 
    	cin>>N>>M;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=1;i<=M;i++) cin>>b[i];
    	int p=0;
    	for(int i=1;i<=N;i++) p=__gcd(p,a[i]-a[1]);
    	for(int i=1;i<=M;i++){
    		v.push_back(abs(__gcd(a[1]+b[i],p)));
    	}
    	for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - A - Codeforces]: https://codeforces.com/contest/1458/problem/A
[7380f034bb90485e9e0d58dcfe3f9919.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/4db55bfb9edd4afd943ffa0f66a3af19.png
[4a1dc6c1e69f42caad889be608d68cf4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/6fee2cc52e3c4a1e9fe4964da6f13561.png

发表评论取消回复

表情：

评论列表（有 0 条评论，60人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #651 (Div. 2) B. GCD Problem

[Problem - 1617B - Codeforces][] 题意：给定一个n，让你构造a,b,c，满足 a+b+c=n，且gcd(a,b)=c 思路：设 c

爱被打了一巴掌/ 2024年03月31日 13:41/ 0 赞/ 82 阅读

相关 Pinely Round 1 (Div. 1 + Div. 2) A. Two Permutations

来写一道\800的题，思路很简单，就是这道题我们应该怎么去严谨地思考 [Problem - 1761A - Codeforces][] ![f38b39e56c3c2d4a

﹏ヽ暗。殇╰゛Y/ 2024年03月30日 17:34/ 0 赞/ 62 阅读

相关【gcd】CF826div2 B

有人不会div2 B 没关系，精神稳定一分钟也很厉害了嘻嘻，嘻嘻.... [Problem - B - Codeforces][] ![2ad3819b26264c2

不念不忘少年蓝@/ 2024年03月22日 17:20/ 0 赞/ 68 阅读

相关【gcd】CF6691div1 A. Row GCD

[Problem - A - Codeforces][] 题意： ![7380f034bb90485e9e0d58dcfe3f9919.png][] 思路：辗转相除法

忘是亡心i/ 2024年03月22日 13:27/ 0 赞/ 61 阅读

相关【MST+GCD】CF714div2 D. GCD and MST

第一次写2000分的题，把大致思路想出来了但是差点细节比如vis数组没加，区间贡献算错了对于这些，思路对的但是差点细节的题，应该多模拟样例，不然写出来会很抽象 [

朱雀/ 2024年03月22日 13:13/ 0 赞/ 59 阅读

相关【组合数学--容斥】CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) D. Count GCD

大概思路想出来了，就差不会写容斥了.... 题意： ![2f7e6497bf284d539796c496ca607e36.png][] ![481d598d1d244b5

小咪咪/ 2024年03月22日 01:34/ 0 赞/ 61 阅读

相关 Codeforces Round #320 (Div. 1) A. A Problem about Polyline

首先明确一点的是，所给的点(a,b)肯定在斜率为负的斜线上面使得x最小。那么我们怎么确定是在哪一条折线呢？看下图： ![这里写图片描述][20150917095658

妖狐艹你老母/ 2022年08月08日 14:44/ 0 赞/ 184 阅读

相关 Codeforces Round #305 (Div. 1) A && B

547A - Mike and Frog 先考虑，从h1\->a1的过程，计算需要的时间如果在M次内，没有到达则不可到达然后再判断是否符合h2\->a2的时间

冷不防/ 2022年08月05日 00:55/ 0 赞/ 185 阅读

相关 VK cup Div1 C. Vulnerable Kerbals （扩展gcd+DAG+最长路）

题目链接： [点击打开链接][Link 1] http://codeforces.com/contest/800/problem/C C. Vulnerable K

浅浅的花香味﹌/ 2022年06月17日 06:27/ 0 赞/ 97 阅读

相关 Codeforces Round #411 (Div. 1)（A~D）题解

题目链接： [\411 (Div. 1)][411 _Div. 1] 差点翻船。题解： A. 这个推导一下，找一下规律就可以了。答案是：ans=(n

￡神魔★判官ぃ/ 2022年06月16日 04:55/ 0 赞/ 147 阅读