意甲冠军：那是， 从数0-n小球进入相应的i%a箱号。然后买一个新的盒子。
今天的总合伙人b一个盒子，Bob试图把球i%b箱号。
求复位的最小成本。
每次移动的花费为y - x ，即移动前后盒子编号的差值的绝对值。
算法：
题目就是要求 
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMjg0MTg0NQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">
先推断 n与 lcm(a,b)的大小，每个周期存在循环。这样把区间缩短避免反复计算。
假设n>lcm(a,b)则 ans = (n/lcm)*solve(lcm)+solve(n%lcm)
否则 ans = solve(n)
设x和y各自等于 i%a和i%b。
我们通过枚举 找规律能发现 t=min(a-x,b-y)是一个段，这一段内abs（x-y)是相等的。
所以仅仅须要用abs(x-y)乘以次数t，在算下一段即可了。
这里要注意t<n-now的情况。本来这一段应该有t个，可是now+t>n了。所以要取t = min(t,n-now）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath> using namespace std; typedef __int64 ll; ll a,b; ll Gcd(ll x,ll y)
{
return y==0?x:Gcd(y,x%y);
} ll abs(ll x)
{
return x>=0? x:(-x);
} ll solve(ll n)
{
ll x=0,y=0,t,v1,v2,now=0;
ll ret = 0;
while(now<n)
{
v1 = a-x;
v2 = b-y;
t = min(v1,v2);
t = min(t,n-now);
ret += t*abs(x-y);
x = (x+t)%a;
y = (y+t)%b;
now += t;
}
return ret;
} int main()
{
int T;
ll n,gcd,lcm,ans;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d",&n,&a,&b);
gcd = Gcd(a,b);
lcm = a*b/gcd;
if(n>=lcm)
ans = solve(lcm)*(n/lcm) + solve(n%lcm);
else ans = solve(n);
printf("%I64d\n",ans);
}
return 0;
}
魔芋真的不适合 搞数学 o(╯□╰)o
版权声明：本文博主原创文章，博客，未经同意不得转载。