题目描述
唐马儒童鞋有收集种子的爱好(真的只是普通的种子)。
他有个n种子,编号为0~n-1。同时他有a个“箱子”,编号为0~a-1。如果一个种子编号为i,它将被放进编号i%a的“箱子”。但是后来时间长了,马儒新建b了个“箱子”,编号为0~b-1,这样就需要把一些种子从原来的a个箱子移动到新的b个箱子,同样的,编号为i的种子将被放进编号i%b的“箱子”。
假设把一个种子从x号箱子移动到y号箱子的花费为|x-y|,童鞋们,你们能帮马儒找出重新安排所有种子需要的花费吗?
【输入描述】
第一行一个整数,表示有 T(1<=T<=10) 组数据。
对于每组数据:
每行代表一组数据,且只有三个整数n,a,b分别代表种子的个数,一开始“箱子”的个数和后来新建“箱子”的个数。
(1<=n<=1,000,000,000, 1<=a,b<=4,000)
【输出描述】
对于每组数据,输出一行:
在这一行输出输出总的花费。
样例
输入
2
8 2 4
11 5 3
输出
8
16
C++ 解法
#include <iostream>
#include <cmath>
using namespace std;
const int N = 5050;
int t,n,a,b;
int dy(int a,int b)
{
if(a<b) swap(a,b);
while(b)
{
int t = a%b;
a = b;
b = t;
}
return a;
}
int main()
{
cin>>t;
getchar();
while(t--)
{
// cin>>n>>a>>b;
long long sum = 0; // sum 一定要 long long
cin>>n>>a>>b;
// dy 函数 求最大公约数
long long k = a*b/dy(a,b); // 那么 k 就是最小公倍数
int c = n/k; // 会有 c 个 最大公倍数周期
int d = n%k;
/*
主要就是下边这个 for 循环 因为 n 最大 为 1e9 并且十组数据
挨个枚举会超时
同时,题目中,给的盒子个数很少,最多 4000;
由此可以想到,我们可以求出,两个盒子的最小公倍数 k
然后我们 枚举 k 次,
最后,再枚举 n%k 次 即可
*/
for(int i=0;i<k;i++)
{
sum += abs(i%a - i%b);
}
sum *= c; // 出来后,要乘以 c
for(int i=0;i<d;i++) // 在对,剩余的数,进行考虑
{
sum += abs(i%a - i%b);
}
cout<<sum<<endl;
}
return 0;
}
嘿嘿,一起加油!
tql
丁宇%%%%%%%%%%%%%%%%%%%%%%%%%