hdu 4611循环节 Balls Rearrangement-白红宇

hdu 4611循环节 Balls Rearrangement

阅读量：4205 次

发布时间：2019-05-26

本文共 1848 字，大约阅读时间需要 6 分钟。

Bob has N balls and A boxes. He numbers the balls from 0 to N-1, and numbers the boxes from 0 to A-1. To find the balls easily, he puts the ball numbered x into the box numbered a if x = a mod A. Some day Bob buys B new boxes, and he wants to rearrange the balls from the old boxes to the new boxes. The new boxes are numbered from 0 to B-1. After the rearrangement, the ball numbered x should be in the box number b if x = b mod B.

　　This work may be very boring, so he wants to know the cost before the rearrangement. If he moves a ball from the old box numbered a to the new box numbered b, the cost he considered would be |a-b|. The total cost is the sum of the cost to move every ball, and it is what Bob is interested in now.

Input

　　The first line of the input is an integer T, the number of test cases.(0<T<=50)

　　Then T test case followed. The only line of each test case are three integers N, A and B.(1<=N<=1000000000, 1<=A,B<=100000).

Output

　　For each test case, output the total cost.

Sample Input

31000000000 1 18 2 411 5 3

Sample Output

08 16 long long  gcd(long long a,long long b){    return b==0?a:gcd(b,a%b);}int main(){    int t;    cin>>t;    while(t--)    {        long long n,a,b;        scanf("%lld%lld%lld",&n,&a,&b);        long long ans = 0;        long long e = a/gcd(a,b)*b;        long long ti = n/e;        long long ty = n%e;        long long now=0;        long long tmp;        long long x=0,y=0;        while(now
    
     e)                tmp=e-now;            ans+=tmp*abs(x-y);            x=(x+tmp)%a;            y=(y+tmp)%b;            now+=tmp;        }        ans*=ti;        now = 0;        x = 0;        y = 0;        while(now
     
      ty)                tmp=ty-now;            ans+=tmp*abs(x-y);            x=(x+tmp)%a;            y=(y+tmp)%b;            now+=tmp;        }        cout<
      
       <

转载地址：http://cvali.baihongyu.com/

你可能感兴趣的文章

Linux安装apache源码包报错:Cannot use an external APR with the bundled APR-util