Balls Rearrangement
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 344 Accepted Submission(s): 165
Problem Description
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
3
1000000000 1 1
8 2 4
11 5 3
Sample Output
0
8
16
Source
2013 ACM/ICPC Asia Regional Online —— Warmup
/*分析：對於i%a - i%b,每次加上從i開始和這個值(i%a - i%b)相等的一段,
這樣i就不是每次+1,而是每次加上一段,如果碰到n大於a,b的最小公倍數，
則只需要計算a,b最小公倍數長度的總和，然後sum*=n/per + p;//p表示前i個數,p=n%per;
本題反思:剛開始自己就是這樣想，但是想到a,b的最小公倍數可能很大,而且n也很大，
如果剛好碰到n<per但是n很大;//per表示a,b最小公倍數，或者碰到n>per但是per很大
即使一段段的算也可能超時，所以一直不敢下手，一直在找尋更簡單的推論。。結果一直沒找到
下次碰到這種情況應該先試試，不能找不出別的更簡單的方法就連自己想到的方法都不試試
現在認真分析發現時間復雜度好像是:O((a/b * min(per,n)/a));//假設a>=b
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<math.h>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=10;
__int64 p;
__int64 Gcd(__int64 a,__int64 b){
if(b == 0)return a;
return Gcd(b,a%b);
}
__int64 calculate(__int64 n,__int64 a,__int64 b,__int64 num){
p=0;
__int64 la=a,lb=b,sum=0,l;
for(__int64 i=0;i<n;){
l=min(la,min(lb,n-i));
if(i+l>num && i<num)p=sum+abs((int)(i%a - i%b))*(num-i);
sum+=abs((int)(i%a - i%b))*l;
i+=l;
la=(la-l+a-1)%a+1;
lb=(lb-l+b-1)%b+1;
}
return sum;
}
int main(){
__int64 n,a,b,t;
scanf("%I64d",&t);
while(t--){
scanf("%I64d%I64d%I64d",&n,&a,&b);
__int64 gcd=Gcd(a,b),per=a*b/gcd,k=min(per,n);//求出最小公倍數
__int64 sum=calculate(k,a,b,n%k);
if(n>per)sum=(n/per)*sum+p;//p表示前n%k個i%a-i%b的和
printf("%I64d\n",sum);
}
return 0;
}
