关于exgcd的总结

Nannan Lv5
  2023-11-05 17:44 2023-11-05 17:44 Created   2024-09-30 19:33:52 2024-09-30 19:33:52 Updated      

关于exgcd的总结

我们主要讨论的是

1.exgcd算法

1.1 关于解的存在性

有裴蜀定理知，对于方程存在解的充分必要条件是：

tips:裴蜀定理 如果均为整数，则有整数使得，这个等式称为裴蜀等式。

1.2exgcd算法介绍

要求，我们可以用求出。令。

当我们求出之后呢，求出的乘上就是答案啦。

具体处理方法就是:

然后对比两边得到：然后只要一直递归下去就啦。

注意边界条件：时候，是解。

1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x = 1,y = 0;
		return a;
	}
	int d = exgcd(b,a%b,y,x);
	y -= (a/b)*x;
	return d;
}

1.3解的通式

对于，假设它的其中一个特解是，那么我们可以求出它的通解：

正确性也很显然，我们感性的去理解一下，因为要保证原式的值不变，那么应该变化相同的倍率。

1.4关于的解

我们知道，对于的题解是：

方程是否有正整数解？

我们发现，

  1. 当同号时：负相关，即越大越小。当求出的是最小的时候，有是最大的。

  2. 当异号时，正相关，即同增同减。

所以，一个合理的想法，我们对传参时候保证的非负性。即：若，那么传入,最后注意讨论变化。

那么如何求解最小正整数解？

由通解可知：

*（）**，相当于保证的情况下减去尽可能多的。注意如果等于了的话再处理一下。

通过就很容易得到

的最小的非负整数解的板子：

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
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll xx,yy;
    ll d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return d;
}

int main()
{
    int _;cin>>_;
    while(_--)
    {
        ll a, b, x, y, m;
        scanf("%lld%lld%lld", &a, &b, &m);
        ll d = exgcd(a, b, x, y);
        if(m % d != 0)
        {
            puts("-1");
            continue;
        }
        a /= d;
        b /= d;
        m /= d;
        ll xx = (ll) x * (m % b) % b;
        if(xx < 0)  xx = xx + b;
        ll yy = (ll)(m - a * xx) / b;
        if(yy < 0)
            puts("-1");
        else
            printf("%lld %lld\n", xx, yy);
    }
}

关于正整数解的个数？

根据通式算出上下界即可。

因为是正整数解那么：

于是

又因为是整数，那么取整一下。同理另一边也是一样的道理。

exgcd求出的特解的范围？

对于，当都不等于且的情况下满足绝对值最小。

在数值上有：.

对于就是

关于正解和非负解的几个结论：

由于我们可以转化成，其中的形式去求解,那么下面只说明的情况：

1.非负整数解

设，其中均为正整数且。

  • 当时，有非负解，且解的个数为或
  • 当时，没有非负解。
  • 当时，恰有个正整数有非负解，具体是哪些不清楚。

2.正整数解

正整数解的个数为：或者

  • 当时有正解
  • 当时无解
  • 当时，恰有个正整数有非负解，具体是哪些不清楚。

推论：

  1. 设且时，是不能表示成形式的最大整数。
  2. 设且时，是不能表示成形式的最大整数。

显然如果可以是负数，那可以表示为任意整数了。

  1. 有解的充要条件是方程有非负解。

exgcd的板子题 

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

ll exgcd(ll a,ll b,ll& x,ll& y)
{
    if(b==0)
    {
        x = 1,y = 0;
        return a;
    }
    ll d = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        ll a,b,c,x,y;
        cin>>a>>b>>c;
        ll d = exgcd(a,b,x,y);
        if(c%d)cout<<-1<<"\n";
        else
        {
            a/=d,b/=d,c/=d;
            x*=c,y*=c;//特解
            //x = x0+tb
            //y = y0-ta
            x = (x%b+b)%b;
            x = x==0?b:x;
            y = (c-a*x)/b;
            if(y>0)
            {
                ll minx,miny,maxx,maxy;
                minx = x,maxy = y;
                y = (y%a+a)%a;
                y = y==0?a:y;
                x = (c-b*y)/a;
                maxx = x,miny = y;
                ll cnt = (maxx-minx)/b+1;//每隔b一个整数解
                cout<<cnt<<" "<<minx<<" "<<miny<<" "<<maxx<<" "<<maxy<<"\n";
            }
            else//有整数解，但无正整数解
            {
                ll minx,miny;
                minx = x;
                y = (y%a+a)%a;
                y = y==0?a:y;
                miny = y;
                cout<<minx<<" "<<miny<<"\n";
            }
        }
    }
    return 0;
}

1.5*取模意义下的一元二次方程的最小值

起源是关于这个题 中提取的思路。

能组成的最小正整数是。但是在取模意义下呢？

考虑以下两个问题：

  1. 的最小值
  2. 的最小值

先说结论：

  1. 的最小值是：
  2. 的最小值是

①先讨论第一个：的最小值

那么我们只要考虑意义下的最小值即可。

设，利用同余性质可知的的倍数，于是，移向得。

tips：同余 设是正整数，若是整数，且,则称和模同余。或者说除以余数为。

显然上面这个柿子已经没有模的意义了，那么上面这个最小显然是

那么的最小值是

②那么对于呢？

上面这个柿子的含义就是要保证的前提下减去尽可能多的，那也就是

有了上面的分析，下面来说这个题 就很容易了。

题目是要求：的最小值，并求出。

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
41
42
43
44
45
46
47
48
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll n,m;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll xx,yy;
    ll d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return d;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m;
    ll sum = 0;
    for(int i = 1; i <= n; i++)
    {
    	ll x;
    	cin>>x,sum += x;
    }

    ll a = n,b = (n+1ll)*n/2,x,y;
    //ax+by=k1g1(mod m)
    ll g1 = exgcd(a,b,x,y);
    //k1g1+tm = k2g2
    ll k1,t;
    ll g2 = exgcd(g1,m,k1,t);
    //ans = min(sum + k2g2)
    ll ans = sum%g2;
    k1 *= ((ans-sum)/g2)%m;
    k1 %= m;
    x*=k1,y*=k1;
    cout<<ans<<"\n";
    cout<<(x%m+m)%m<<" "<<(y%m+m)%m<<"\n";
    return 0;
}

1.6 一些习题练习

1.I. Step

思路：由题意转化得：我们要求出的最小的。

设，那么题目转化为

设

即：

问题转化为求：的最小的,即求的最小的。不妨假设，且,我们设那么，移向得：,这里用得到最小的。

显然互质的，我们可以考虑对质因数分解，把不同种的质因数分配到上(二进制枚举方案)即可，

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

ll lcm(ll a,ll b)
{
    return a/__gcd(a,b)*b;
}
vector<ll>a;
map<ll,ll>mp;
void primer(ll x)
{
    for (ll i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
        {
            int s = 0;
            a.push_back(i);
            mp[i] = 1;
            while (x % i == 0)
            {
                x = x / i;
                s++;
                mp[i]*=i;
            }
        }
    }
    if (x > 1)a.push_back(x),mp[x] = x;;
}

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll xx,yy;
    ll d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return d;
}
 

ll p[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i = 1;i <= n; i++)
        cin>>p[i];
    ll LCM = p[1];
    for(int i = 1;i <= n; i++)
        LCM = lcm(LCM,p[i]);
    ll t = LCM*2;
    primer(t);
    int sz = a.size();
    ll ans = 1e18;
    for(int i = 0;i < (1<<sz); i++)
    {
        ll A = 1,B,x,y;
        for(int j = 0;j < sz; j++)
        {
            if((i>>j)&1)A*=mp[a[j]];
        }
        B = t/A;
        ll d = exgcd(A,B,x,y);
        //ax+1=by
        //-ax+by = 1
        x = -x;
        x = (x%(B/d)+(B/d))%(B/d);
        if(A*x!=0)
        {
            ans = min(ans,A*x); 
        }
    }
    cout<<ans<<"\n";
    return 0;
}

2.A. Modulo Ruins the Legend

思路：上面讲解exgcd的时候有讲，主要思想就是，先去除取模的意义。什么意思呢？

就是说对于后的最小值即的最小值

即的最小值。这样我们处理出没有取模意义的等式就可以计算啦。






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
41
42
43
44
45
46
47
48
49
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll n,m,sum;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll xx,yy;
    ll d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return d;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m;
    for(int i = 1;i <= n; i++)
    {
        ll x; cin>>x,sum += x;
    }
    ll a = n,b = (n+1)*n/2,x,y,k1,t;
    ll g1 = exgcd(a,b,x,y);
    ll g2 = exgcd(g1,m,k1,t);
    //ax+by = k1g1 (mod m)
    //k1g1+tm = k2g2
    //ans = min(sum + k2g2) = sum%g2
    //k2 = ((ans-sum)/g2)%m
    //k1*=k2
    //x*=k1,y*=k1;
    ll ans = sum%g2;
    cout<<ans<<"\n";
    ll k2 = (ans-sum)/g2%m;
    k1*=k2,k1%=m;
    x *= k1,y*=k1;
    cout<<(x%m+m)%m<<" "<<(y%m+m)%m<<"\n";


    return 0;
}

3.M-Water_“范式杯”2023牛客暑期多校训练营1

思路：不妨假设

显然的时，

因为不可能同时为负数，那么当异号的时候呢？

不妨假设

对于以下的讨论不妨假设且,于是：

含义就是喝杯,贡献是，再喝杯水。

对于需要分步考虑：

  1. 将倒满
  2. 将中水导入,此时杯中：的水
  3. 将的水喝掉
  4. (*)将第二个杯子里面的倒掉（如果是最后一步就不要这一步）

那么

最后答案就是

接下来我们只需先求出一个特解，然后在特解附件去求它的通解就可以了。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll xx,yy;
    ll d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return d;
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        ll A,B,X,x,y;
        cin>>A>>B>>X;

        ll d = exgcd(A,B,x,y);
        if(X%d){
            cout<<"-1\n";
            continue;
        }
        else{
            //x = xxA+yyB
            //x = (xx+yy-yy)A+yyB
            //x = (xx+yy)A+(-yy)(A-B)
            //ans1 = 2*(xx+yy)
            //ans2 = 4*(-yy-1)+3
            //ans1+ans2 = 2xx+2yy-4yy-4+3 = 2xx-2yy-1
            A /= d;
            B /= d;
            X /= d;
            ll xx = (ll) (x % B) * (X % B) % B;
            ll yy = (ll)(X - A * xx) / B;
   
            ll ans = 1e18;
            for(int i = -10;i <= 10; i++)
            {
                ll nx = (xx + B*i),ny = (yy - A*i);
                if(nx>=0 && ny>=0)
                    ans = min(ans,2*(nx+ny));
                else ans = min(ans,2*abs(nx-ny)-1);
            }
            cout<<ans<<"\n";
            
            
        }
       
    }

    return 0;
}

4.Red-Black Pepper

思路：由于我们只能在一个店买，该商店红辣椒份一包，黑辣椒份一包，且只能买整包的。那么要求买到份数恰好是，那么就有，含义是在第家店买包红的和包黑的总共份。

第道菜用了红辣椒可以增加的美味值，用黑的增加。

我们设为买份红的可以达到的最大美味值。

我们先考虑一个简单的问题：买份红的，份黑的的最大美味值是多少？

让我们感性的去理解一下：假设我全买了黑的，再用贪心的策略把其中份换成红的。

全买黑的贡献，对于第道菜换成红的

那么我们按照从大到小排序，贪心的去选那个红的。

我们观察是单减的，可能由某一个(可能是正数)逐渐减小变成负数。

那么我们由一个先增后减的趋势，是个有极值的函数(开口向下)。

那么处理好了，接下来考虑询问。

很显然的解用可解。

我们先求出来了的一个特解

如果说，那就无解直接。

否则的话继续讨论。

特解知道了，我们可以进一步求出它们的通解：

回归问题

对于

因为是有极值的单峰函数，我们可以暴力一遍找到最大值和最大值的横坐标

对于通解：

显然最小取，最大取

那么对于通解的最小值就是，最大值就是

然后我们在从任意集中，选择离下标最近的两组，取两者的即可。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
ll n,m,c[N],f[N],a[N],b[N];
bool cmp(int a,int b)
{
    return a>b;
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll xx,yy;
    ll d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return d;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n;
    for(int i = 1;i <= n; i++)
        cin>>a[i]>>b[i],c[i] = a[i]-b[i],f[0]+=b[i];
    sort(c+1,c+1+n,cmp);
    for(int i = 1;i <= n; i++)f[i] = f[i-1]+c[i];
    ll high = 0,maxv = f[0];
    
    for(int i = 1;i <= n; i++)
        if(f[i]>maxv)high = i,maxv = f[i];
    cin>>m;
    while(m--)
    {
        ll a,b,x,y;

        cin>>a>>b;
        ll g = exgcd(a,b,x,y);
        if(n%g){
            cout<<"-1\n";
            continue;
        }
        x = x*(n/g)%(b/g);
        if(x<0)x+=(b/g);
        if(a*x>n){
            cout<<"-1\n";
            continue;
        }
        /*
            x = x0+b/g*t
            y = y0-a/g*t

            ax+by = n

            ax = ax0+ab/g*t
            by = ay0-ab/g*t

            ax = ax0+dt
        */
        ll d = a/g*b;//lcm
        //ax+by = n
        //ax+t[a,b] = ax+td
        //ax+td = n
        //t = (n-ax)/d
        //t的最小值显然是0，最大值是(n-ax)/d
        ll mi = a*x,mx = n-(n-a*x)%d;
        ll ans = max(f[mi],f[mx]);
        if(high>=mi && high<=mx)
        {
            ll l = high-(high-mi)%d;//下取整
            ll r = high+(mx-high)%d;//上取整
            ans = max(ans,max(f[l],f[r]));
        }
        cout<<ans<<"\n";
    }
    return 0;
}

5.Two Arithmetic Progressions

题意：给定.要求找出中的的数量，使得满足。

思路：题目要求

我们移向得：，写成我们常见写法就是。

显然我们可以用直接判无解的情况。那么对于有解的情况呢？

首先因为参数有负数，那么我们可以知道，是同增同减的。我们可以求得一组最小的。怎么求呢？

我们可以直接通过求得一组特解。我们令

那么通解就是：

又由于是同增同减的，那么我们要找到一组最小的解，当且仅当：

或

我们令

那么我们的通解就变成了：

因为我们要求有多少属于的，那么我们把代入得：

那么可以取的的个数就是我们的答案了。

即：

接下来我们只需要求出和即可，答案就是

注意：取整要手写，因为当其是负数时候，c++默认往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
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll xx,yy;
    ll d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return d;
}

ll floordiv(ll a,ll b)
{
	//因为当其是负数时候，c++默认往0取整，所以下取整我们要自己写
	if(a%b==0)return a/b;
	else if(a>0)return a/b;
	else return a/b-1;
}

ll ceildiv(ll a,ll b)
{
	if(a%b==0)return a/b;
	else if(a>0)return a/b+1;
	else return a/b;
}

int main()
{
	ll a1,b1,a2,b2,l,r,x,y;
	cin>>a1>>b1>>a2>>b2>>l>>r;
	ll d = exgcd(a1,a2,x,y);
	y = -y;
	if((b2-b1)%d){
		cout<<"0\n";
		return 0;
	}
	x *= (b2-b1)/d,y *= (b2-b1)/d;
	ll dx = abs(a2/d),dy = abs(a1/d);
	x = (x%dx+dx)%dx,y = (a1*x-(b2-b1))/a2;
	if(y<0)y = (y%dy+dy)%dy,x = (a2*y+(b2-b1))/a1;
	ll kmin = max(0ll,ceildiv(l-a1*x-b1,a1*dx));
	ll kmax = floordiv(r-a1*x-b1,a1*dx);
	cout<<max(0ll,kmax-kmin+1)<<"\n";
	return 0;
}

6.Integers Have Friends

思路：这个题是关于的题，在说这个题之前，我们先说下面这两个题目

CF1216D Swords

题意：一共有种剑，并且每种初始值为把，然后进来个人，他们在剧院的地下室没人拿走把剑（这z把剑是属于同一种类型的），并且不同的人可以拿同种的剑；现在给出每种还剩下的剑，问最小的值是多少？

思路：很显然，因为初始每个种类数量是一样的，可以确定初始每个的数量是当前剩余量的最大值,因为如果比最大的还大，那我不就需要更多人取拿了吗，显然不是最优的了，那么我们令，表示每个类型的消失数量。又因为每个人只能拿把同类型的剑，并且不同人可以拿同一种。那么答案显然是.

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    ll maxv = 0;
    for(int i = 1;i <= n; i++)
    {
        cin>>a[i];
        maxv = max(maxv,a[i]);
    }
    ll ans = 0;
    for(int i = 1;i <= n; i++)
    {
        a[i] = maxv-a[i];
    }
    ll g = a[1];
    for(int i = 1;i <= n; i++)
        g = __gcd(g,a[i]);
    for(int i = 1;i <= n; i++)
        ans += a[i]/g;
    cout<<ans<<" "<<g<<"\n";
    
    return 0;
}

Array Stabilization (GCD version)

题意：给定长度为的序列，下标从，每次操作构造新的序列，满足，再将序列替换为序列，问最少多少次操作后满足序列所有元素相同。

思路：考虑对于～的元素，考虑变化一次每个元素变为了什么？举个例子：.变化一次之后就是。那么变化两次呢？

看到这里，变化就很明显了。题目问的是最小操作次数，也很显然，这个操作次数满足单调性，因为次满足那么次也一定满足。那么考虑二分。如何呢？就是确定最小前缀，并且后面的都等于。

那么我们需要一个快速处理出区间的方法，那显然就是表啦，当然线段树也可以。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// AC one more timesk
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int LOGN = 20;
int a[N],n;
struct S_T {
    // op 函数需要支持两个可以重叠的区间进行合并
    // 例如 min、 max、 gcd、 lcm 等
    int f[22][N], lg[N];
    void build(int n) {
        lg[0] = -1;

        for (int i = 1; i <= n; ++i) {
            f[0][i] = a[i];
            lg[i] = lg[i / 2] + 1;
        }

        for (int i = 1; i <= 20; ++i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                f[i][j] = __gcd(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
    }
    int query(int l, int r) {
        if(l <= n && r > n)return __gcd(query(l,n),query(1,r-n));
        int len = lg[r - l + 1];
        return __gcd(f[len][l], f[len][r - (1 << len) + 1]);
    }
} ST;

bool judge(int k)
{
    int t = ST.query(1,1+k-1);
    for(int i = 2;i <= n; i++)
        if(ST.query(i,i+k-1) != t)return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        ST.build(n);
        int l = 1,r = n;
        while(l <= r)
        {
            int mid = (l+r)>>1;
            if(judge(mid))r = mid-1;
            else l = mid+1;
        }
        cout<<r<<"\n";
    }
    return 0;
}

说完上面两个题，接下来来说这个 题

题意：

  • 给定 和一个长度为 的数组 ，求一个最长的区间 ，使得存在 和 ，对于所有 （即区间内所有数对 取模余数相等），输出最长区间长度（区间长度定义为 ）。
  • 有多组测试数据。

思路：令

那么就有:

对于任意两项：比如

即：

那结论就是：若在的意义下相等，一定能整除

也就是说，任意两项差是的倍数。

我们可以对原序列做差得到新数列，因为，那么新数列符合条件的区间一定不为。(因为不妨设最后取模之后为0，区间的就是我们求的)

我们考虑枚举，然后二分。部分用表。

小细节：

  1. 多组数据，注意清空
  2. 特判的情况
  3. 因为做差得的新数组只有项，最大子区间长度应该+1才是答案。
  4. 开 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int LOGN = 20;
ll a[N],b[N],n;
struct S_T {
    // op 函数需要支持两个可以重叠的区间进行合并
    // 例如 min、 max、 gcd、 lcm 等
    ll f[22][N], lg[N];
    void build(int n) {
        lg[0] = -1;

        for (int i = 1; i <= n; ++i) {
            f[0][i] = a[i];
            lg[i] = lg[i / 2] + 1;
        }

        for (int i = 1; i <= 20; ++i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                f[i][j] = __gcd(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
    }
    void clear(int n)
    {
         for (int i = 1; i <= 20; ++i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                f[i][j] = 0;
    }
    ll query(int l, int r) {
        if(l <= n && r > n)return __gcd(query(l,n),query(1,r-n));
        int len = lg[r - l + 1];
        return __gcd(f[len][l], f[len][r - (1 << len) + 1]);
    }
} ST;

//a≡b(mod m)
//m|(a-b)

signed main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>b[i];
        for(int i = 1;i < n; i++)
            a[i] = abs(b[i]-b[i+1]);
        if(n==1){
            cout<<1<<"\n";
            continue;
        }
        n--;
        ST.clear(n);
        ST.build(n);
       
        int ans = 0;
        //枚举左端点二分右端点
        for(int i = 1;i <= n; i++)
        {
            int l = i,r = n;
            if(a[i]==1)continue;
            while(l<=r)
            {
                int mid = (l+r)>>1;
                if(ST.query(i,mid)>1)l = mid+1;
                else r = mid-1;
            }
            ans = max(ans,l-1-i+1);
        }
        cout<<ans+1<<"\n";
    }
    return 0;
}

7.E. Identical Parity

思路：思维+

我们可以把题目看成一个长度为的区间在长度为的数组上滑动。每当我们前进一格，如果出去一个，那么下一个必须进来一个，如果出去一个，那么下一个必须进来一个。那意味着什么呢？

对于下标为:

上的奇偶性要是一样的，即。

我们考虑按上述方法把原序列按照下标分成块，每块去分配奇偶性。

包含数字个数为的块数有块，包含数字个数为的块数有块。

又由于整个序列上应该有个位置是奇数，有个位置上是偶数。

那么就考虑

含义就是：取个长度为的，和个长度为的放奇数(恰好填满所有奇数，剩下的放偶数就可以了。那么只需要我们的是不是满足。

如何判断呢？考虑先用求出一个特解。

那么通解就是。

那么：
由于要求是整数，就是说②④式有分数，为了处理这个问题，两边同乘得
接下来看这两个不等式两边有没有交集，再确定区间里面有没有的倍数，这样能保证是整数。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a/b*x;
    return d;
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        ll a = n/k+1,b = n/k,m = (n+1)/2,x,y;
        ll d = exgcd(a,b,x,y);
        if(m % d){
            cout<<"No\n";
            continue;
        }
        a /= d;
        b /= d;
        m /= d;
        ll xx = (ll) x * (m % b) % b;
        if(xx < 0)  xx = xx + b;
        ll yy = (ll)(m - a * xx) / b;
        if(yy < 0 || xx > n % k)
            cout<<"No\n";
        else
        {
            if(0<=xx&&xx<=n%k&&0<=yy&&yy<=k-(n%k))cout<<"Yes\n";
            else{
                ll l1 = -xx*a,r1 = (n%k-xx)*a;
                ll l2 = -(k-n%k-yy)*b,r2 = yy*b;
                ll l = max(l1,l2),r = min(r1,r2);
                ll ab = a*b;
                if(l>r)cout<<"No\n";
                else if(r/ab>0&&r/ab*ab>=l)cout<<"Yes\n";
                else cout<<"No\n";
            }
        }
    }
    return 0;
}

  • Title: 关于exgcd的总结
  • Author: Nannan
  • Created at : 2023-11-05 17:44:00
  • Updated at : 2024-09-30 19:33:52
  • Link: https://redefine.ohevan.com/2023/11/05/关于exgcd的总结/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
关于exgcd的总结
  1. 关于exgcd的总结
    1. 1.exgcd算法
      1. 1.1 关于解的存在性
      2. 1.2exgcd算法介绍
      3. 1.3解的通式
      4. 1.4关于的解
        1. 方程是否有正整数解？
        2. 那么如何求解最小正整数解？
        3. 关于正整数解的个数？
        4. exgcd求出的特解的范围？
        5. 关于正解和非负解的几个结论：
    2. 1.5*取模意义下的一元二次方程的最小值
    3. 1.6 一些习题练习
      1. 1.I. Step
      2. 2.A. Modulo Ruins the Legend
      3. 3.M-Water_“范式杯”2023牛客暑期多校训练营1
      4. 4.Red-Black Pepper
      5. 5.Two Arithmetic Progressions
      6. 6.Integers Have Friends
        1. CF1216D Swords
        2. Array Stabilization (GCD version)
      7. 7.E. Identical Parity