最近也是在备战比赛，所以也是来小小的复习了一下以前学的东西
最重要的是第一道题！
最重要的是第一道题！
最重要的是第一道题！
先放拓欧板子（不懂怎么推出了就发在评论区或者私聊）
int exgcd(int a,int b,int &x,int &y)
{if(b==0){x=1,y=0;return a;}int x2,y2;int d=exgcd(b,a%b,x2,y2)x=y2;y=x2-a/b*y2;return d;
}例题：
P2054 [AHOI2005] 洗牌
我们先来通过6张牌来列举一下
初始 [ 1 , 2 , 3 , 4 , 5 , 6 ]
第一次 [ 4 , 1 , 5 , 2 , 6 , 3 ]
第二次 [ 2 , 4 , 6 , 1 , 3 , 5 ]
第三次 [ 1 , 2 , 3 , 4 , 5 , 6 ]
我们通过上面对1这个数据分析，
初始值在1位置，第一次变换后在2位置，第二次变换后在4位置，第三次变换后在1位置
我们发现每次都相当于乘2，但是为什么会被突然折断呢？我们不难想到可能是存在取模操作
因此我们可以大胆猜想这个数是7，也就是（n+1）
我们再对3这个数据进行分析
初始值在3位置，第一次在6位置，第二次再5位置，第三次在3位置
我们发现也是每次位置都乘2，然后取模7（n+1）
因此我们就发现了规律
第i个数m次操作后的位置为 ：( i* 2^m)%(n+1)
但是题意问的是m次操作之后，谁在L这个位置，不是问你每个数在哪，而是问你在特定位置的数，很明显，我们一开始想的是遍历一遍所有数，找到谁在那个位置，但是数据是10^10，很明显会超时，因此我们只能去倒推一遍 这个式子
假设x在L那个位置，那么
(2^m)*x= (n+1) *k + L
请问你看这个式子想到了什么？？？
我嘞个豆，啥也没想到，你是要毁了我吗？孩子
那我再给你将这个式子变一下形式
(2^m)*x + (n +1) *y = L 这下能看出来拓展欧几里得的形式了吧
为什么能用拓欧呢？因为题目上说了，n是一个偶数，n+1一定是个奇数，2^m次方一定是个偶数，所以肯定互质的
但是这个式子也很麻烦，能不能再变一下呢？那肯定是可以的
我们先去求
(2^m)*x + (n +1) *y = 1，然后最后给x乘以L不就是了，说罢，我的气息终于不再掩饰，顷刻将代码炼化出来
77pts
#include <bits/stdc++.h>
using namespace std;
#define int long long int n, m, l;
int mod; int fast(int a, int b, int mod)
{ int result = 1; int base = a % mod; while (b > 0) { if (b % 2 == 1) { result = (result * base) % mod; } base = (base * base) % mod; b /= 2; } return result;
} 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, x, y); int x2 = x; x = y; y = x2 - (a / b) * y;return d;
} signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> l; mod = n + 1; int x, y; int f = fast(2, m, mod);int z = exgcd(f, mod, x, y); x = (x+mod) % mod; cout << (x*l) % mod << '\n';
} 没想到被暗算了，在运算过程中有可能会导致超出long long的范围，因此需要用到龟速幂，也就是在乘法的过程中用快速乘去运算
84pts
#include <bits/stdc++.h>
using namespace std;
#define int long long int n, m, l;
int mod; int mul(int a,int b)
{int result=0;while(b>0){if(b%2==1){result=(result+a)%mod;}a=(a+a)%mod;b/=2;}return result%mod;
}int fast(int a, int b)
{ int result = 1; int base = a % mod; while (b > 0) { if (b % 2 == 1) { result=mul(result,base);} base = mul(base,base); b /= 2; } return result%mod;
} 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, x, y); int x2 = x; x = y; y = x2 - (a / b) * y;return d;
} signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> l; mod = n + 1; int x, y; int f = fast(2, m);int z = exgcd(f, mod, x, y); x = (x+mod) % mod; cout << (x*l) % mod << '\n';
} 为什么还是错一个点嘞？左思右想都没想明白，
才发现，在逆元前面还是有可能会爆数据，为什么不能用乘法逆元的积性函数的性质，我先去求2和n+1的逆元然后再去m次方后再去乘以L，思考便后，我便不再掩饰自己的气息，仿佛有成尊之势
果然AC了
100pts
#include <bits/stdc++.h>
using namespace std;
#define int long long int n, m, l;
int mod; int mul(int a,int b)
{int result=0;while(b>0){if(b%2==1){result=(result+a)%mod;}a=(a+a)%mod;b/=2;}return result%mod;
}int fast(int a, int b)
{ int result = 1; int base = a % mod; while (b > 0) { if (b % 2 == 1) { result=mul(result,base);} base = mul(base,base); b /= 2; } return result%mod;
} int exgcd(int a,int b,int &x,int &y)
{if(b==0){x=1,y=0;return a;}int x2,y2;int d=exgcd(b,a%b,x2,y2);x=y2;y=x2-a/b*y2;return d;
}signed main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> l; mod = n + 1; int x, y; exgcd(2, mod, x, y); x = (x+mod) % mod; x=fast(x,m);cout<<mul(x,l) << '\n';
} P5656 【模板】二元一次不定方程 (exgcd)
思路：题目不是很难，但是处理的条件颇多，只要有耐心并且细心一点都可以写出来
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int a,b,c;
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}
int exgcd(int a,int b,int &x,int &y)
{if(b==0){x=1,y=0;return a;}int x2,y2;int d=exgcd(b,a%b,x2,y2);x=y2;y=x2-a/b*y2;return d;
}
signed main()
{cin>>t;while(t--){int x,y;int d;int minnx,minny,maxnx,maxny;int cnt=0;cin>>a>>b>>c;d=gcd(a,b);if(c%d!=0){cout<<-1<<"\n";}else{a/=d,b/=d,c/=d;exgcd(a,b,x,y);x*=c,y*=c;if(x>0&&x%b!=0){minnx=x%b;}else{minnx=x%b+b;}maxny=(c-minnx*a)/b;if(y>0&&y%a!=0){minny=y%a;}else{minny=y%a+a;}maxnx=(c-minny*b)/a; if(maxnx>0){cnt=(maxnx-minnx)/b+1;}if(cnt==0){cout<<minnx<<" "<<minny<<"\n"; }else{cout<<cnt<<" "<<minnx<<" "<<minny<<" "<<maxnx<<" "<<maxny<<"\n";}}}return 0;
}
P1516 青蛙的约会
思路：这题我们可以写出一个方程
假设第一只青蛙的起始位置为n，速度为a，第二只青蛙的起始位置为m，速度为b
可以写出方程
(a-b)*t+L *y=m-n
想到了什么？当然是拓欧
直接去写拓欧去求出最小的x，然后x*（m-n）/gcd(a-b,L)即可，当然不要忘记取模L
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a,b,l;
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}int exgcd(int a,int b,int &x,int &y)
{if(b==0){x=1,y=0;return a;}int x2,y2;int d=exgcd(b,a%b,x2,y2);x=y2;y=x2-a/b*y2;return d;
}signed main()
{int x,y;cin>>n>>m>>a>>b>>l;if(a<b){swap(a,b),swap(n,m);}a=a-b;b=l;int d=gcd(a,b);int c=(m-n+l)%l;exgcd(a,b,x,y);if(c%d!=0){cout<<"Impossible\n";return 0;}l/=d;cout<<(c/d*x%l+l)%l;return 0;
}P3951 [NOIP2017 提高组] 小凯的疑惑
思路：其实就是看自己的思维的，如果想要能够被表示那么就说明x和y都要大于0，所以不能表示的最小数一定为
-a+?*b（？表示现在还不知道）
那为什么一定为这种形式呢？
x不能等于-2吗？
肯定可以啊，只不过一定不是最大，因为还有一个x=-1的时候更大
那么？的范围是什么，最大是(a-1)
为什么呢？假如可以为a的话，那么方程就可以化简为a*(b-1)，那么就可以用a类型钞票单独表示了
最后就可以写出-a+b*(a-1)
也就是a*b-a-b;
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{int a,b;cin>>a>>b;cout<<(a*b-a-b);return 0;
}
