辗转相除法——数组和的关系

辗转相除法——数组和的关系

辗转相除法求最大公约数

以一个具体例子来说明辗转相除法的流程：

输入：119 85

输出：17

更相减损术：

119-85=34，85-34=51，51-34=17，34-17=17

辗转相除：

119/85=1…34，85/34=2…17，34/17=2…0

两式子做一下处理，发现其原理相同：

119=85+34，85=34+51，51=34+17，34=17+17

119=85+34，85=2✖️34+17，34=2✖️17

证明做法的正确性：

先证明更相减损术。首先有g|a,g|b,g|(a+-b)，所以119-85=34中119和85的公约数也是119-85=34的因数；由于公约数是85的因数，也是34的因数，所以85-34=51中85和34的公约数为51的因数；由于公约数是34的因数，也是51的因数，所以51-34=17中51和34的公约数为17的因数；由于公约数是34的因数，也是17的因数，所以34-17=17中34和17的公约数为17的因数；发现已经收缩到了一个不能够再拆分的值了，所以答案即为17

再证明辗转相除法。首先知道a%b=0,gcd(a,b)=b，只证明辗转两次的情况，两次以上可以用归纳法证明。a%b=c , b%c=0时，可得c为最大公约数，因为b%c=0，所以b=mc，那么a=nb+c=(mn+1)c，由于m和mn+1肯定互质，所以最大公约数为c

应用之一(于数组和的关系当中)

代码源 数学

题目：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-43I2uRvw-1667058195869)(/Users/chenyanling/Library/Application Support/typora-user-images/image-20221029230857390.png)]

题解：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7v2FasJd-1667058195869)(/Users/chenyanling/Library/Application Support/typora-user-images/image-20221029231042596.png)]

稍微写详细一点，我们要求最大的gcd(a,b)，也就是求gcd(a,m)或者gcd(b,m)最大值，当a或者b为m的因子时，gcd(a.m)或者gcd(b,m)最大，所以可以通过先求m的最小因子来求最大因子，那么这个最大因子就是我们的答案，也是我们的a,b其中一个

代码

#include 

using namespace std;
typedef long long LL;

int divide(int x){//找x的最小因子
    for(int i=2;i<=x/i;i++)
        if(!(x%i))return i;
    return x;
}

int main(){
    int n;
    cin>>n;

    int d;
    if(n&1) d=min(divide(n),divide((n+1)/2));//因为数据范围太大，所以分割成两部分来找最小因子
    else d=min(divide(n/2), divide(n+1));

    LL res;
    if(n<=2)res=1;//但要注意特判，2分割之后所得最小因子已经大于2了，故不能再用上述方法
    else res=(LL)n*(n+1)/2/d;

    cout<<res<<endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2019女生赛 B.Gcd

题目：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6qtwBhfS-1667058195870)(/Users/chenyanling/Library/Application Support/typora-user-images/image-20221029232538249.png)]

上面一题就是女生赛原题

C. Minimize the Thickness

题意：问一个数组能否被划分为所有段之和相同，若能，输出所有划分情况中最长段最小的长度

题解：正面想；暴力分段看和是否相等，或者暴力枚举和看能否划分成功，一眼爆炸且复杂。反向思考，也算是优化第二种暴力；去分析可以划分成哪些和，即求出数组和，枚举数组和的因子，由于答案一定是数组和的因子，所以枚举大集合，锁定有答案的小集合，即检验因子能否作为段之和去成功划分

代码

#include 

using namespace std;
const int N=2010;

int n,a[N];

int check(int k) {//检验以段之和为k来划分段是否可行
    int res=0,len=0,sum=0;
    for(int i=1;i<=n;i++) {
        sum+=a[i]; len++;
        if(sum==k) { res=max(res,len); len=0; sum=0; }
        if(sum>k) return 0;
    }
    return res;
}

void solve() {
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    
    int ans=0x3f3f3f3f;
    for(int i=1;i*i<=sum;i++) {//枚举因子
        if(sum%i==0) {
            int t=check(i);
            if(t) ans=min(ans,t);//检验答案是否符合要求，更新答案
            t=check(sum/i);
            if(t) ans=min(ans,t);
        }
    }
    cout<<ans<<'\n';
}

int main() {
    int t; cin>>t;
    while(t--) solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40