学步园

传送门

题意是要我们把已经按序号放入A类盒子的球放入B类盒子，问其中操作所需要的移动距离为多少。

因为球的数量为10^9盒子也是10^5的数量级

如果一个一个球的去计算的话很容易TLE，所以就按段求和，每一个移动距离相同的段我们进行统一计算

这样每次差不多最多计算A+B次，这样就避免了TLE的问题了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <map>

using namespace std;

long long gcd(long long x,long long y)
{
    //cout<<x<<' '<<y<<endl;
    if(x % y != 0)
    {
        return gcd(y,x%y);
    }
    return y;
}

long long lcm(long long x,long long y)
{
    long long c = gcd(x,y);
    //cout<<x<<' '<<y<<' '<<c<<endl;
    return x * y / c;
}

long long n,a,b,ans,sum,wei,lun,aa,bb,add,ll;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d%I64d%I64d",&n,&a,&b);
        long long l = lcm(a,b);
        wei = n % l;
        lun = n / l;
        //cout<<l<<' '<<wei<<' '<<lun<<endl;
        ll = ans = sum = 0;
        while(ll < l)
        {
            add = abs(ll % a - ll % b);
            int c = min(a - ll % a,b - ll % b);
            if(c + ll < l)
            {
                sum += c * add;
                ll += c;
            }
            else
            {
                sum += (l - ll) * add;
                ll = l;
            }
        }
        ll = 0;
        while(ll < wei)
        {
            add = abs(ll % a - ll % b);
            int c = min(a - ll % a,b - ll % b);
            if(c + ll < wei)
            {
                ans += c * add;
                ll += c;
            }
            else
            {
                ans += (wei - ll) * add;
                ll = wei;
            }
        }
        ans += sum * lun;
        printf("%I64d\n",ans);
    }
    return 0;
}