AC（今天不想起标题）

接着挑战数论题

我找到了一个传新的方法求逆元，区别于逆元1的费马小定理，我想用扩展欧几里得算法

我们把题目符号化

找到一个b，使得a×b≡1(mod p)，其中，a，p已知

那首先的要求就是a与p互质，那么这件事就成了这样的不定方程

ax+py=gcd(a,p)=1

那不就扩展欧几里得算法的原样吗

接下来，用递归实现之前，做个小证明

∵gcd(a,p)==gcd(p,a%p)(辗转相除法)&&ax+py=gcd(a,p)(原式)&&a%b=a-[a/b]b（众所周知）

∴xb+y(a-[a/b]b)=gcd(a,b)（等量代换）

∴ya+(x-y[a/b])b=gcd(a,b)(提公因式)

那么，根据这个写递归就好了

#include<iostream>
using namespace std;
void get(int a,int p,int &gcd,int &x,int &y)
{
	if(p==0)
	{
		x=1;
		y=0;
		gcd=a;
		return;
	}
	get(p,a%p,gcd,y,x);
	y-=a/p*x;
	return;
}
int main()
{
	int a,p;
	cin>>a>>p;
	int x,y,gcd;
	get(a,p,gcd,x,y);
	if(gcd!=1)
		cout<<"No solution";
	else
		cout<<(x+p)%p;
	return 0;
 } 

（关于排行榜调到第二名）排行榜的名次不重要，反正跟着自己的节奏走就完了，咱不用通过Ctrl+C，Ctrl+V的方式来刷排名，只要能自己写好代码，学到知识就是好的，重点是在赛场上的表现而不在于刷题的速度