ACM – Uva10673 – 扩展gcd

点击量:21

水题一发。。直接使用floor和ceil函数,然后暴力即可。。。

如果使用快速的方法,就是扩展gcd。其中d的初始值没有关系,最后返回的是gcd(a,b).

暴力算法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(b, -1, sizeof(b))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
// ax + by = d
// 扩展gcd
void gcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if(!b) { d = a; x = 1; y = 0; }
    else { gcd(b, a%b, d, y, x);  y-= x*(a/b);  }
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int T;
    cin >> T;
    ll x, k;
    while(T--)
    {
        scanf("%lld%lld", &x, &k);
        double c = x/(double)k;
        ll fl = floor(c);
        ll ce = ceil(c);
        // printf("%lld %lld\n", a, b);
        bool find = 0;
        for(ll i = 0; !find; i++)
            for(ll j = 0; i * fl + j *ce <= x; j++)
            {
                if(i*fl + j *ce == x)
                {
                    printf("%lld %lld\n", i, j);
                    find =1;
                    break;
                }
            }
    }
    return 0;
}

扩展gcd算法

速度更快,0.012

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(b, -1, sizeof(b))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
// ax + by = d
// 扩展gcd
void gcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if(!b) { d = a; x = 1; y = 0; }
    else { gcd(b, a%b, d, y, x);  y-= x*(a/b);  }
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int T;
    cin >> T;
    ll x, k;
    while(T--)
    {
        scanf("%lld%lld", &x, &k);
        double c = x/(double)k;
        ll fl = floor(c);
        ll ce = ceil(c);
        ll a1, a2, g;
        gcd(fl, ce, g, a1, a2);
        a1 *= x/g;
        a2 *= x/g;
        printf("%lld %lld\n", a1, a2);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注