[HOJ 403] 史萊姆突變計畫

作法：

對於第 i 種的史萊姆，他突變之後會固定變成另外一種的史萊姆，假設叫作 p[ i ] 好了，那麼考慮一張 n 個點的圖，對於每個 i 都往 p[ i ] 連一條有向邊，那麼這張圖就會變成水母圖。而對屬的部份也可以建一張圖。所以當給定一個起點的屬的時候，考慮沿著 p 一直跳，那麼他有一天一定會跳到重複的點，這時候就會一直重複下去，這樣的圖形就長的像一條鍊接上一個環。而給定起點的種的時候就沿著 y 座標的排列一直跳，也會跳到重複的點。所以現在就得到了兩個圖，一個是 x 得意個是，這時候就可以分成好幾種情況討論，首先是如果詢問的屬（或種）沒辦法被跳到，那麼就一定不可能。另一種可能是目標點的 x 值落在 x 的圖的鍊上，那麼我們就知道跳幾次會跳到終點了，所以就可以直接判斷了。同理當目標點的 y 值落在 y 的圖的鍊上也可以直接確認。而如果兩個都在環上的話，因為走到環上任意一點的可能步數會形如 a * x + b ，其中 x = 0 , 1 , ... ， a 為環的大小。而另一個環也是這樣，因此就會變成要解 a * x + b = c * y + d 了，其中 x 和 y 是未知數，且都 >= 0 ，而這就可以用擴展歐基里得算法做了。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100000+10 ;
 
void gcd(LL a,LL b,LL &x,LL &y,LL d)
{
    if(b==0) { x=d/a ; y=0 ; return ; }
    gcd(b,a%b,y,x,d) ;
    y-=(a/b)*x ;
}
 
LL solve(LL a,LL b,LL c,LL d) /// ax+b = cy+d , return ax+b or -1
{
    LL x,y , g=__gcd(a,c) ;
    if((d-b)%g) return -1 ;
    gcd(a,-c,x,y,d-b) ;
    while(x>=0 || y>=0) x-=c/g , y-=a/g ;
    while(x<0 || y<0) x+=c/g , y+=a/g ;
    return a*x+b ;
}
 
int x[maxn],y[maxn] ;
int visx[maxn],visy[maxn] ;
int pth1[maxn],pth2[maxn],cnt1=0,cnt2=0 ;
int a1,b1,a2,b2 ; /// sx use a1 steps to cycle, cycle size = b1.
main()
{
    int n,m,sx,sy,Q ; scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&Q) ;
    for(int i=0;i<n;i++)
    {
        int t ; scanf("%d",&t) ;
        x[i]=((LL)i*t)%n ;
    }
    for(int i=0;i<m;i++)
    {
        int t ; scanf("%d",&t) ;
        y[i]=((LL)i*t)%m ;
    }
 
    memset(visx,-1,sizeof(visx)) ;
    memset(visy,-1,sizeof(visy)) ;
    for(int i=sx;;i=x[i])
    {
        if(visx[i]!=-1) { a1=visx[i] , b1=cnt1-visx[i] ; break ; }
        visx[i]=cnt1 ; pth1[cnt1]=i ; cnt1++ ;
    }
    for(int i=sy;;i=y[i])
    {
        if(visy[i]!=-1) { a2=visy[i] , b2=cnt2-visy[i] ; break ; }
        visy[i]=cnt2 ; pth2[cnt2]=i ; cnt2++ ;
    }
 
    while(Q--)
    {
        int ex,ey ; scanf("%d%d",&ex,&ey) ;
        if(visx[ex]==-1 || visy[ey]==-1) { printf("-1\n") ; continue ; }
        if(visx[ex]<a1)
        {
            int tmp=visx[ex] ;
            int id= (tmp<a2 ? tmp : ((tmp-a2)%b2+a2)) ;
            printf("%d\n",pth2[id]==ey ? tmp : -1) ;
        }
        else if(visy[ey]<a2)
        {
            int tmp=visy[ey] ;
            int id= (tmp<a1 ? tmp : ((tmp-a1)%b1+a1)) ;
            printf("%d\n",pth1[id]==ex ? tmp : -1) ;
        }
        else printf("%lld\n",solve(b1,visx[ex],b2,visy[ey])) ;
    }
}