HDU 4611 - Balls Rearrangement(2013MUTC2-1001)(数学,区间压缩)

以前好像是在UVa上貌似做过类似的,mod的剩余,今天比赛的时候受baofeng指点,完成了此道题

此题题意:求sum(|i%A-i%B|)(0<i<N-1)

A、B的循环节不同时,会有重叠,重叠后的区间里的数的值相等(可以证明,这里不给出了),然后压缩区间端点值,直接求区间和即可

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define LL long long
using namespace std;
LL abs(LL a,LL b)
{
return (a-b)>(b-a)?(a-b):(b-a);
}
LL gcd(LL a,LL b)
{
return b==0?a:gcd(b,a%b);
}
LL lcm(LL a,LL b)
{
return a/gcd(a,b)*b;
}
LL t[200005];
LL d[200005];
LL f[200005];
int main()
{
int T;
LL n,a,b;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d",&n,&a,&b);
LL x=lcm(a,b);
LL A=(x/a);
LL B=(x/b);
LL ct=0;
for(LL i=1;i<=A;i++)
{
t[i]=i*a;
}
for(LL i=1;i<=B;i++)
{
t[A+i]=i*b;
}
sort(t+1,t+A+B+1);
d[ct++]=0;
d[ct++]=t[1];
for(LL i=2;i<=A+B;i++)
{
if(t[i]!=t[i-1])
d[ct++]=t[i];
}
for(LL i=1;i<ct;i++)
{
f[i]=abs(d[i-1]%a,d[i-1]%b)*(d[i]-d[i-1]);
}
for(LL i=1;i<ct;i++)
f[i]+=f[i-1];
LL ans=0,INT=n/x,MOD=n%x;
ans+=INT*f[ct-1];
for(LL i=1;i<ct;i++)
{
if(k<=d[i])
{
ans+=f[i-1]+abs(d[i-1]%a,d[i-1]%b)*(MOD-d[i-1]);
break;
}
}
printf("%I64d\n",ans);
}
return 0;
}
上一篇:虚拟机NUMA和内存KSM


下一篇:Python ->> 第一个Python程序