1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include <stdio.h> #include <vector> using namespace std; vector<int> s, t, r, q; int i; void INIT_EEC_Table(int A, int B){ s.clear(); t.clear(); r.clear(); q.clear(); s.push_back(1); s.push_back(0); t.push_back(0); t.push_back(1); r.push_back(A); r.push_back(B); q.push_back(0); q.push_back(A/B); } void EEC(int A,int B){ INIT_EEC_Table(A,B); i = 1; while(r[i-1]%r[i]){ r.push_back(r[i-1] - r[i] * q[i]); s.push_back(s[i-1] - s[i]*q[i]); t.push_back(t[i-1] - t[i]*q[i]); ++i; q.push_back(r[i-1]/r[i]); } } int main(int argc, char** argv) { int A, B; int T,N,test_case; scanf("%d",&T); for (test_case = 1; test_case <= T; test_case++){ scanf("%d %d",&A,&B); EEC(A,B); printf("#%d %d %d\n",test_case,s[i],t[i]); } return 0; }
|