这就没什么说的了，好好读题就行。

1 #include
        
          2 #include
         
           3 #include
          
            4 using namespace std; 5  6 int main() 7 { 8     int n; 9     cin>>n;10     int a1,b1,a2,b2;11     int ok=5;12     cin>>a1>>b1;13     if(a1!=b1) ok=0;14     for(int i=1;i
           
            >a2>>b2;17         if(a2!=b2) ok=0;18         if(ok==5&&a1
           
          
         
        

 

每一步转移时两种决策，加100或者减50

1 #include
        
          2 #include
         
           3 #include
          
            4 using namespace std; 5 const int maxn=2000010; 6 int vis[maxn]; 7 int p,x,y; 8 int check(int n) 9 {10     int i=(n/50)%475;11     int ct=0;12     for(;ct<25;ct++)13     {14         i=(i*96+42)%475;15         if(i+26==p) return 1;16     }17     return 0;18 }19 20 struct node21 {22     int x,d;23     bool operator<(const node &f)const24     {25         return d>f.d;26     }27 }now,nex;28 29 int bfs()30 {31     int ans=1e9;32     memset(vis,0,sizeof(vis));33     now.x=x;34     now.d=0;35     vis[x]=1;36     priority_queue
           
             q;37     q.push(now);38     while(!q.empty())39     {40         now=q.top();41         q.pop();42         int xx=now.x;43         if(check(xx)) return now.d;44         if(xx-50>=y&&!vis[xx-50])45         {46             nex.x=now.x-50;47             nex.d=now.d;48             vis[xx-50]=1;49             q.push(nex);50         }51         if(!vis[xx+100])52         {53             nex.x=now.x+100;54             vis[xx+100]=1;55             nex.d=now.d+1;56             q.push(nex);57        }58     }59     return ans;60 }61 62 int main()63 {64 65     cin>>p>>x>>y;66     int ok=bfs();67     if(ok==1e9) printf("-1\n");68     else printf("%d\n",ok);69 70 }
           
          
         
        

 

由题意可得，

(x+a)/(y+b)=p/q

x+a=k*p ,  y+b=k*q

a=k*p-x ,  b=k*q-y

我们要求的是b的最小值，显然b关于k单调，二分查找k的最小值即可。

（第一反应是扩展欧几里得-_-||）

1 #include 
       
         2 #include 
        
          3 #define LL long long 4  5 int main() 6 { 7     int n; 8     int x,y,p,q; 9     scanf("%d",&n);10     while(n--)11     {12         scanf("%d%d%d%d",&x,&y,&p,&q);13         LL l=0,r=0x3f3f3f3f;14         LL ans=-1;15         while(l<=r)16         {17             LL m=(l+r)/2;18             LL a=m*p-x;19             LL b=m*q-y;20             if(a>=0&&b>=0&&a<=b)21             {22                 r=m-1;23                 ans=b;24             }25             else l=m+1;26         }27         printf("%lld\n",ans);28     }29 }