水题一发。。直接使用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 = ; 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 = ; } 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 = ; for(ll i = ; !find; i++) for(ll j = ; i * fl + j *ce <= x; j++) { if(i*fl + j *ce == x) { printf("%lld %lld\n", i, j); find =1; break; } } } return ; }
扩展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 = ; 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 = ; } 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 ; }