企业网站html百度云,可视化小程序开发工具,郑州做网站那家做的好,网站建设宗旨是指题目 Sheng bill有着惊人的心算能力#xff0c;甚至能用大脑计算出两个巨大的数的GCD#xff08;最大公约 数#xff09;#xff01;因此他经常和别人比 赛计算GCD。有一天Sheng bill很嚣张地找到了你#xff0c;并要求和你比 赛#xff0c;但是输给Sheng bill岂不是很丢… 题目 Sheng bill有着惊人的心算能力甚至能用大脑计算出两个巨大的数的GCD最大公约 数因此他经常和别人比 赛计算GCD。有一天Sheng bill很嚣张地找到了你并要求和你比 赛但是输给Sheng bill岂不是很丢脸所以你 决定写一个程序来教训他。 输入格式 共两行 第一行一个数A。 第二行一个数B。 0 A , B ≤ 10 ^ 10000。 输出格式 一行表示A和B的最大公约数。 输入样例 12 54 输出样例 6 题解 时隔大半年我回来A这道题啦【当初写的太BUG了】 求GCD很容一想到辗转相除而高精不好操作取模这就用到了辗转相除法的本质更相减损法 GCD(a,b) GCD(a,a-b) 【a 】 然而这样会T所以我们还要优化 GCD(a,b) 2*GCD(a/2,b/2) 【2|a且2|b】 GCD(a,b) GCD(a/2,b) 【2|a】 GCD(a,b) GCD(a,b/2) 【2|b】 GCD(a,b) GCD(a,a-b) 【a 】 加上个压位高精【高精减法高精除低精高精乘低精高精比较】 就可以A了 #includeiostream
#includecstdio
#includecstring
#includestring
#includealgorithm
#define LL long long int
#define REP(i,n) for (int i 1; i (n); i)
using namespace std;
const int maxn 10005,B 4,Base 10000,maxm 100005,INF 1000000000;
struct NUM{int s[maxn],len;NUM() {memset(s,0,sizeof(s)); len 0;}
};
istream operator (istream in,NUM a){string s;ins;int temp 0,t 1;for (int i s.length() - 1; i 0; i--){temp temp t * (s[i] - 0);if (t * 10 Base) a.s[a.len] temp,temp 0,t 1;else t * 10;}if (temp) a.s[a.len] temp;return in;
}
ostream operator (ostream out,const NUM a){if (!a.len) out0;else {printf(%d,a.s[a.len]);for (int i a.len - 1; i 0; i--) printf(%04d,a.s[i]);}return out;
}
bool check(const NUM a){return !(a.s[1] 1);}
bool equal(const NUM a,const NUM b){if (a.len ! b.len) return false;REP(i,a.len) if (a.s[i] ! b.s[i]) return false;return true;
}
bool operator (const NUM a,const NUM b){if (a.len b.len) return true;if (a.len b.len) return false;for (int i a.len; i 0; i--){if (a.s[i] b.s[i]) return true;if (a.s[i] b.s[i]) return false;}return false;
}
void Half(NUM a){int carry 0,temp;for (int i a.len; i 0; i--){temp (a.s[i] carry * Base) / 2;carry a.s[i] carry * Base - temp * 2;a.s[i] temp;}while (!a.s[a.len]) a.len--;
}
void Twice(NUM a){int carry 0,temp;for (int i 1; i a.len; i){temp a.s[i] * 2 carry;a.s[i] temp % Base;carry temp / Base;}while (carry) a.s[a.len] carry % Base,carry / Base;
}
NUM operator -(const NUM a,const NUM b){NUM c; c.len a.len;int carry 0,temp;for (int i 1; i a.len; i){temp a.s[i] - b.s[i] carry;if (temp 0) carry -1,temp Base;else carry 0;c.s[i] temp;}while (!c.s[c.len]) c.len--;return c;
}
int main(){NUM A,B; int cnt 0;cinAB;while (!equal(A,B)){if (check(A) check(B)) Half(A),Half(B),cnt;else if (check(A)) Half(A);else if (check(B)) Half(B);else {if (B A) swap(A,B);B B - A;}}while (cnt--) Twice(A);coutAendl;return 0;
}转载于:https://www.cnblogs.com/Mychael/p/8282745.html
