首页 > ACM题库 > HDU-杭电 > HDU 3597-BOMB-数论-[解题报告]HOJ
2014
11-27

HDU 3597-BOMB-数论-[解题报告]HOJ

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;
}
参考:http://blog.sina.com.cn/s/blog_677a3eb30100q05a.html


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept