小北
0%

扩欧和线性同余

发表于 更新于 分类于

前面还留有博客没补完，先将扩欧和线性同余写了吧！

扩展欧几里得

扩展欧几里得定理：对于两个不全为0的整数a，b,必存在一组解使ax+by==gcd(a,b);
若ax+by==m有解，那么gcd(a,b)就是m的因子;
若ax+by==1有解，那么gcd(a,b)==1; 

1
2
3
4
5
6
7
int gcd(int a,int b)
{
	if(b==0)
	return a;
	else
	return gcd(b,a%b);
}

这是求最大公约数的代码，所以我们可以将上述等式做一下改变
即：
ax+by==gcd(a,b)==gcd(b,a%b)
ax+by
==bx1+(a%b)y1
==bx1+(a-a/bb)y1
==a*y1+b(x1-(a/b)y1)
所以ax+by==a*y1+b(x1-(a/b)y1)
所以上一层的x是下一层的y1，上一层的y是下一层的x1-(a/b)y1
当到达最后一层时b==0，gcd(a,b)==a;所以ax+by==a；
所以x==1，y==0；

代码如下：

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

例

天才程序员菜哭武和张老师有一天到一个城市旅游，旅途中菜哭武觉得无聊就想和张老师玩一个游戏。菜哭武有n个石子，每个石子都标有1到n之间到数，且各不相同，一开始他们会随机从这堆石子选一个石子放置到一个集合中，张老师选的数是a，菜哭武选的是b（a和b不相同）。接下来菜哭武和张老师轮流按照如下规则拿走一个石子：当石子x能被拿走时，当且仅当集合存在y和z，满足x等于y+z或者y-z，当x被拿走时，把它放到集合中。谁完成最后一轮操作时，谁获胜。张老师总是先手，于是张老师就好奇当决定好a和b时，他是否总是能获胜，你能帮助一下张老师吗？ 张老师和菜哭武的游戏

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
#include<stdio.h>

int gcd(int a,int b)
{
    return !b?a:gcd(b,a%b);
}

int main()
{
    int n;
    int a,b;
    int t;
    int i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&a,&b);
        int gcdd=gcd(a,b);
        int x=n/gcdd;
        if(x&1)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

线性同余