hdu 4611

2013hdu多校联赛二的第一题，当时队友说两个盒子个数的最小公倍数是周期，

如果两个数的最小公倍数比较大的时候（最大是9999900000），如果遍历求的话肯定会超时

当时想找各种规律，都没找到，最后我想到了一种遍历的优化，就是每次不是只增加一个数，

求出最大mi个球在两个盒子的序号都是递增的，那么每次只需要加上第一项差值的mi陪，

球的序号加上mi，肯定比每次加1要快，把遍历的区间缩短了。

结果一看求出最大的9999900000答案瞬间出来了，信心大增，结果wrong了几次

当时有个想法把变量都改成64位的，以前做题的时候遇到过这样的问题，

如果64位跟int混合运算会出现错误，改完之后abs函数有个警告，就又改回去了，

当时有几个答案跟暴力出来的结果不一样总以为有什么情况没考虑到，就没太在意这个问题，

今天改完64位，一下就A了，那个后悔啊，，，，，，，，，，，，，，，，，，，，，，，，

#include <stdio.h>

#include <string.h>

__int64 gcd(__int64 a,__int64 b)

{

    if(b==0)return a;

    else return gcd(b,a%b);

}

__int64 abs(__int64 a)

{

	if(a>0)return a;

	return -a;

}

__int64 cont(__int64 n,__int64 a,__int64 b)

{

    __int64 ans,i,mi;

    i=0;ans=0;

	while(i<n)

	{

		mi=(a-i%a)>(b-i%b)?(b-i%b):(a-i%a);

		if(i+mi>=n)

			mi=n-i;

		ans+=abs(i%a-i%b)*mi;

		i+=mi;

	}

	return ans;

}

int main()

{

    int T;

    __int64 n,a,b,t;

    __int64 ans;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%I64d%I64d%I64d",&n,&a,&b);

		t=gcd(a,b);

		t=a*b/t;

        if (t>=n)	ans=cont(n,a,b);

        else ans=cont(t,a,b)*(n/t)+cont(n%t,a,b);

        printf("%I64d\n",ans);

    }

    return 0;

}

巴特西

hdu 4611

最新文章

热门文章