80,时间超了最后两个
查看原帖
80,时间超了最后两个
1076087
2023111206li楼主2024/7/7 18:37
#include <bits/stdc++.h>
using namespace std;
#define Max 123456789
inline void read(long long& a)
{
    long long s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    a = s * w;
}

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    long long n;
    read(n);
    for (int i = 0; i < n; i++)
    {
        bool flag1 = 0, flag2 = 0;
        long long a, b, c;
        read(a), read(b), read(c);
        if (a < b)
            swap(a, b), flag1 = 1;
        long long u = a, v = b,a1=0,b1=0,a2=0,b2=0;//u是最大公约数,v是最小公倍数
        while (v)
        {
            long long temp = u % v;
            u = v;
            v = temp;
        }
        v = a * b / u;
        while (++a1 * a <= min(v,c-1))
        {
            if (!((c - a1 * a) % b))
            {
                flag2 = 1;
                break;
            }
        }
        if(flag2)
        {
            long long total = (c - a1 * a) / v + 1;
            if (!(c % a)) total--;
            a2 = a1 + (total - 1) * (v / a);
            b1 = (c - a2 * a) / b;
            b2 = (c - a1 * a) / b;
            if (flag1)
                swap(a1, b1), swap(a2, b2);
            printf("%lld %lld %lld %lld %lld\n", total,a1, b1, a2, b2);
        }
        else
        {
            a1 = 0,flag2=0,b1=0;
            if (c % a == 0)
            {
                b1 = v/b;
                goto out;
            }
            if (c % b == 0)
            {
                a1 = v / a;
                goto out;
            }
            while (++a1 * a <= v)
            {
                if (!((c + a1 * a) % b))
                {
                    flag2 = 1;
                    b1 = (c + a1 * a) / b;
                    break;
                }
            }
            if (flag2)
            {
            out:
                if (b1) swap(a1, b1), swap(a, b), flag1= !flag1;
                b1 = ((c) - a1 * a) / b;
                while (b1 <= 0)
                {
                    b1 += v / b;
                }
                if (flag1)
                    swap(a1, b1);
                printf("%lld %lld\n", a1, b1);
            }
            else
                printf("-1\n");
        }
    }
    return 0;
}
2024/7/7 18:37
加载中...