[HDOJ3430 Shuffling]【解一元同余方程组】【例题】

【题目大意】
先有一个1,2,3..n的序列。
给定一个置换群。
然后再给出一个目标状态。
求用置换群置换几次到达目标状态？
【算法分析】
暴力求出各循环节。与错位的次数。
得到p个形如 x = ci (mod mi)的方程。
mi并非两两互质，所以不能使用中国剩余定理。
我们可以通过类似中国剩余定理的方法求解。
今天我在HDU比赛时最后一直在推这个同余方程组怎么求。。。
额，以前没写过，于是果断沙茶，大家一起来鄙视我。。。
后来再推了一阵，又看了一下师傅的推导，虽然和我的不大相同，但方向应该没错。
在后来。。。找了个大神的模板过来看。。。我晕，就是有一个地方mod的数打错了。。。
现在记录一下的我的推导过程。
使用类似数学归纳法的思想：
首先，对于同余方程 x = ci (mod mi)的一个解x。那么x + k * mi依然是该方程的一个解。而且同时，这样能取遍该同余方程的所有解。
我们考虑假设已经找到了一个最小自然数解x，满足了前i-1个同余方程。
那么，我们现在要让x满足第i个方程的同时，仍然满足前i-1个方程，那么我们只能取形如这样的数：
x + k * LCM (其中LCM代表(m1,m2,m3…mi-1)的最小公倍数)。
好了，那么新的第i个同余方程变成
(x+k*LCM) = ci (mod mi)    ————————其中x，LCM，ci，mi已知。
于是变成 k * LCM + t * mi = ci-x。这个方程就可以利用拓展欧几里得算法的求解。
具体是调用 ex_gcd(LCM,mi,k,t)得出一个k*LCM+t*mi=gcd(LCM,mi)的解。（关于k，t）
然后k*(ci-x)/gcd(LCM,mi)可以得出真正要求的红色式子中的k。
接着就是将一个适合的k带进红色的式子。
这一步就很容易出错了，我在比赛时就是这里错了。。。= =
考虑我们在exgcd那一步求得的方程：k*LCM+t*mi=gcd(LCM,mi)。
它本质上是： k * (LCM / gcd(LCM,mi)) + t* (mi / gcd(LCM,mi))=1
所以假设（k,t）是一组可行解，那么所有的可行解可以这么表示：
（k + p*mi / gcd(LCM,mi) , t – p*LCM / gcd(LCM,mi) ）。（其中p为整数）
于是我们可以将k%( mi / gcd(LCM,mi) )。那么得到的数必然也是一个可行的k。（并且是最小自然数解）
这样的k自然是最合适的，我们把它带进红色式子。
那么得到新的x，然后再更新一下lcm，合并到最后，就得出一个最小整数解x。
【CODE】
#include #include #include #include using namespace std;
const int N=525;
typedef __int64 lld;
int n,cnt;
int next[N],Final[N],v[N];
int L[N],P[N];
lld m[N],c[N];
bool check;

void init(){
check=true;
cnt=0;
memset(v,0,sizeof(v));
for (int St=1;St<=n;St++)
if (!v[St]){
int i=St,Num=0,j,k;
cnt++;
while (!v[i]){
v[i]=1;
L[++Num]=i;
P[Num]=Final[i];
i=next[i];
}
bool Same=false;
for (i=1;i<=Num;i++)
if (P[i]==L[1]){
Same=true;
j=i; k=1;
do{
if (P[j]!=L[k]) Same=false;
j=j%Num+1;
k=k%Num+1;
}while (i!=j);
break;
}
if (!Same) check=false;
m[cnt]=Num;
c[cnt]=(Num-(i-1))%Num;
}
}

lld exgcd(lld a,lld b,lld &x,lld &y){
if (!b){
x=1;
y=0;
return a;
}
else{
lld res=exgcd(b,a%b,x,y);
lld t=x;
x=y;
y=t-(a/b)*y;
return res;
}
}

lld mod(lld x,lld y){
lld res=x%y;
if (res<0) res+=y;
return res;
}

void solve(){
n=cnt;
check=true;
lld ans=c[1],LCM=m[1],x,y,g,mm;
for (int i=2;i<=n;i++){
g=exgcd(LCM,m[i],x,y);
if ((c[i]-ans)%g) {check=false; return;}
ans=mod( ans + LCM * mod( (c[i]-ans)/g*x, m[i]/g ) , LCM/g*m[i]);
LCM=LCM/g*m[i];
}
printf("%I64dn",ans);
}

int main(){
while (1){
scanf("%d",&n); if (!n) break;
for (int i=1;i<=n;i++) scanf("%d",&next[i]);
for (int i=1;i<=n;i++) scanf("%d",&Final[i]);
init();
if (!check) puts("-1");
else{
solve();
if (!check) puts("-1");
}
}
}