学步园

找规律，模拟，计算压缩;

最大公因数，最小公倍数

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
/**
    ∑abs(i%A - i%B) 0<=i<N
*/
ll getGCD ( ll a, ll b )
{
    for ( int t; b; )
    {
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}
ll getLCM ( ll a, ll b )
{
    return a * b / getGCD ( a, b );
}
ll mabs ( ll a )
{
    return a > 0 ? a : -a;
}
ll solve ( ll lcm , ll a, ll b )
{
    ll res = 0;
    ll lasta = 0, lastb = 0, last ;
    ll numa = 0, numb = 0;
    for ( last = 0; last < lcm; )
    {
        if ( lasta + a <= lastb + b )
        {
            lasta = min(a+lasta, lcm) ;
            res += ( lasta - last ) * mabs ( numa - numb );
            numa = 0;
            numb = ( lasta - last + numb ) % b;
            last = lasta;
        }
        else
        {
            lastb = min(b+lastb, lcm) ;
            res += ( lastb - last ) * mabs ( numa - numb );
            numb = 0;
            numa = ( numa + lastb - last ) % a;
            last = lastb;
        }
    }
    return res;
}
int main()
{
#ifdef  __GNUC__
    freopen ( "in.txt", "r", stdin );
#endif // __GNUC__
    int t;
    ll n, a, b, lcm, res;

    scanf ( "%d", &t );
    while ( t-- )
    {
#ifdef  __GNUC__
        scanf ( "%lld%lld%lld", &n, &a, &b );
#else
        scanf ( "%I64d%I64d%I64d", &n, &a, &b );
#endif // __GNUC__
        if ( a < b ) { swap ( a, b ); }
        lcm = getLCM ( a, b );
        res = solve ( lcm, a, b );
        res = res * ( n / lcm );
        lcm = n % lcm;
        res += solve ( lcm, a, b );
#ifdef  __GNUC__
        printf("%lld\n", res);
#else
        printf("%I64d\n", res);
#endif // __GNUC__

    }
    return 0;
}