感觉和辗转相除相似,考虑证明正确性
设当前 Alice
的橙子、苹果数为 \(a_0,a_1\),Bob
同理,考虑构造状态矩阵
\(\begin{pmatrix}
a_0 & b_0\\
a_1 & b_1\\
\end{pmatrix}\),那么初始状态 \(I\) 为
\(\begin{pmatrix}
1 & 0\\
0 & 1\\
\end{pmatrix}\),那么 \(A\) 操作相当于
\(\times
\begin{pmatrix}
1 & 1\\
0 & 1\\
\end{pmatrix}\),\(A\) 操作相当于
\(\times
\begin{pmatrix}
1 & 0\\
1 & 1\\
\end{pmatrix}\)
设 \(f(M)=\frac{a_0+b_0}{a_1+b_1}\),相当于需要将 \(f(I)\) 变为 \(\frac{x}{y}\),考虑矩阵乘法对 \(I\) 的改变,但是发现并不好做,由于知道最终状态,那么考虑倒序求解,设 \(P\) 为当前状态,且可以拆分为 \(P=AP'\)(下一步状态),若 \(f(P')=\frac{a+b}{c+d}=\frac{n}{m}\),那么 \(f(P)=\frac{a+b+c+d}{c+d}=\frac{n+m}{m}\),相当于 \(f(P)=\frac{n}{m}\),若 \(n>m\),\(f(P')=\frac{n-m}{m}\),否则 \(f(P')=\frac{n}{m-n}\),那么自然地利用辗转相除法求出此次乘上的是 \(A\) 还是 \(B\) 了
#include<bits/stdc++.h>
using namespace std;
long long x,y;
void exgcd(long long a,long long b){
if(a>b){
if(b!=1) printf("%lldA",a/b),exgcd(a%b,b);
else printf("%lldA",a-1);
}
else{
if(a!=1) printf("%lldB",b/a),exgcd(a,b%a);
else printf("%lldB",b-1);
}
}
int main(){
scanf("%lld%lld",&x,&y);
if(__gcd(x,y)==1) exgcd(x,y);
else printf("Impossible");
return 0;
}
标签:begin,frac,CF585C,Alice,long,pmatrix,printf,end,Bob
From: https://www.cnblogs.com/zyxawa/p/18328051