首页 > ACM题库 > HDU-杭电 > HDU 4611-Balls Rearrangement[解题报告]HOJ
2015
09-17

HDU 4611-Balls Rearrangement[解题报告]HOJ

Balls Rearrangement

问题描述 :

  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.

输入:

  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).

输出:

  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).

样例输入:

3
1000000000 1 1
8 2 4
11 5 3

样例输出:

0
8
16

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long gcd(long long a,long long b){
	return b ? gcd(b,a % b) : a;
}
long long lcm(long long a,long long b){
	return a / gcd(a,b) * b;
}
long long get(long long n,long long a,long long b){
	long long ans = 0,tem = 0,x = 0,y = 0,now = 0;
	while(now < n){
		tem = min(a - x,b - y);
		if(tem + now > n)tem = n - now;
		ans += tem * abs(x - y);
		x = (x + tem) % a;
		y = (y + tem) % b;
		now += tem;
	}
	return ans;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t --){
		long long n,a,b;
		//scanf("%I64d%I64d%I64d",&n,&a,&b);
		cin>>n>>a>>b;
		long long ans = 0;
		long long l = lcm(a,b);
		if(n > l)ans = get(l,a,b) * (n / l) + get(n % l,a,b);
		else ans = get(n,a,b);
		//long long ans = get(lcm(a,b),a,b) * n / lcm(a,b) + get(n % lcm(a,b),a,b);
		//printf("%I64d\n",ans);
		cout<<ans<<endl;
	}
	return 0;
}