題目連結:HDU 4710 Balls Rearrangement
題意:不啰嗦了;
提煉出來就是求
思路:
容易得到結果就是 一個數列的是以lcm(a,b)為循環節的一個數列,答案就是求和這個數列。掃一遍的話lcm(a,b)很大會爆掉(比賽爪機的在一個循環節中for了一遍 = =)。
大神的做法:在算一個循環節中跳着求和,比如: 20 5 3
紅色框(代碼中的t)中是是以 %a為0到 %b為0,%b為0到 %a為0。這一段段中的花費是一樣的。(這裡就減少時間複雜度)。
解釋下為什麼是花費一樣:seq數列是等差遞增的,那麼這段數列( 指的是 %a為0到 %b為0 或者 %b為0到 %a為0 )對a,b取摸後的值遞增是不變的,是以上(%a)下(%b)的差不變。
x,y的差就是算相同花費中的一個花費
#include <stdio.h>
#define LL __int64
#include <algorithm>
using std::min;
LL iabs(LL a)
{
if(a<0) return -a;
return a;
}
LL find(LL a,LL b,LL c)
{
LL x=0,y=0,t,p=0,q;
LL ans=0;
while(p<c)
{
t=min(a-x,b-y);
if(t+p>=c)
t=c-p;
ans+=t*abs((LL)(y-x));
x=(x+t)%a;
y=(y+t)%b;
p+=t;
}
return ans;
}
LL gcd(LL a,LL b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
LL lcm(LL a,LL b)
{
return a/gcd(a,b)*b;
}
int main()
{
LL ans;
LL t,sum;
LL n,a,b,i,g;
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d%I64d%I64d",&n,&a,&b);
g=lcm(a,b);
sum=0;
/* p[1]=p[0]=0;
for(i=0;i<g;i++)
{
sum+=iabs((i%a)-(i%b));
p[i]=iabs((i%a)-(i%b));
}*/
/*for(i=0;i<g;i++)
printf("%I64d ",p[i]);
printf("\n");*/
ans=find(a,b,g)*(n/g)+find(a,b,n%g);
printf("%I64d\n",ans);
}
return 0;
}
/*
10
20 2 4
30 5 3
8 2 4
11 5 3
*/