2014
11-27

# BOMB

Our space military base is under attack.The virus break into our computer,and destroy the CCS(Carrier Control System).Carrier is a kind of spaceship,which has the most powerful weapon.We have tried several times to find out the way to take control of them again.Unfortunately,at last we realized that our carriers are not belong to us anymore.We nosed out that our enemy who comes from Chars,a planet with many wise cultures living in,had embezzled the command of the carriers from us.Soon after,We recived a command from our SCO(space command office).It says we have to destroy all the uncontrollable carriers.
According to the information report we got from our spy organization,All the uncontrollable carriers are fly in a circle rail.To make a easier problem,we divide the circle into equal N(N<=100000000) parts and number it from 0 to N-1. We can consider that the length every part of rail is 1.In light of our report,there are M(M<=100000) carriers are uncontrollable.The number i uncontrollable carrier is at the middle of the number p[i](0<=p[i]<=N-1) rail.To destroy the carriers,we have M remote control bombs.The number I bombs is at the middle of the number q[i](0<=q[i]<=N-1) rail.We can let a bomb move to a carrier.When it move from number i rail to number i+1(or number i-1) rail it cost 1 energy(bombs in number N-1 rail can move to number 0 rail ,it also cost 1 energy;Remember bombs cannot leave the rail ) .The more energy we used when we move,The less damage we can make to the carriers.Clearly, We must spend the minimal energy to move all the bombs on to the carrier.One bombs can just destroy one carrier,even two carrier are at the same place.
We can imagine that carrier do not move.

There are several test case.
For each test case: The first line contain 2 integers.N,M. Then followed 2*m lines,1..m line contain p[i],and m+1..2*m lines contain q[i];

There are several test case.
For each test case: The first line contain 2 integers.N,M. Then followed 2*m lines,1..m line contain p[i],and m+1..2*m lines contain q[i];

10 4
0
1
2
3
8
9
4
5

8

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ll __int64
#define maxn 7
ll mm[maxn],rr[maxn];//n个数，mm除数，rr余数
ll exgcd(ll a,ll b,ll &x,ll &y){
//求gcd(a,b)=ax+by
ll
t,d;
if (b==0)
{x=1;y=0;return a;}
d=exgcd(b,a
%b,x,y);
t=x;
x=y;
y=t-a/b*y;
return
d;
}
ll gcd(ll x,ll y){
if(y==0){return y;}
return
gcd(y,x%y);
}
ll China_remain(ll n){
ll
m1,m2,r1,r2,d,c,t,i;
bool
flag=0;
m1=mm[0],r1=rr[0];
for ( i = 0;
i < n – 1; i++){
m2=mm[i+1];
r2=rr[i+1];
ll x,y;
d = exgcd(m1, m2,x,y);
c = r2 – r1;
if (c % d){flag = 1;break;}
x=x*c/d;
t=m2/d;
x=(x%t+t)%t;
r1=m1*x+r1;
m1=m1*m2/d;
}
if
(flag)return -1;
else{
if
(r1==0&&n>1){
r1=mm[0];for(i=1; i<n; i++)r1=gcd(mm[i],r1);
ll ans=1;for( i=0; i<n; i++)ans*=mm[i];
r1=ans/r1;
}
if(r1==0&&n==1)r1=mm[0];
return r1;
}
}
int main(){
ll
i,T,n,C=1;
//
freopen(“a.txt”,”r”,stdin);
scanf(“%I64d”,&T);
while(T–){
scanf(“%I64d”,&n);
for(i=0;i<n;i++){
scanf(“%I64d”,&mm[i]);
}
for(i=0;i<n;i++){
scanf(“%I64d”,&rr[i]);
}
ll ans=China_remain(n);
printf(“Case %I64d: %I64d\n”,C++,ans);
}
return
0;
}