{"id":270,"date":"2010-06-02T12:55:00","date_gmt":"2010-06-02T04:55:00","guid":{"rendered":"http:\/\/localhost\/?p=270"},"modified":"2010-06-02T12:55:00","modified_gmt":"2010-06-02T04:55:00","slug":"sdoi2009supergcd","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=270","title":{"rendered":"[SDOI2009]SuperGCD"},"content":{"rendered":"\n

[SDOI2009]SuperGCD<\/p>\n

Time Limit:4000MS Memory Limit:65536K
Total Submit:34 Accepted:6
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

Sheng bill\u6709\u7740\u60ca\u4eba\u7684\u5fc3\u7b97\u80fd\u529b\uff0c\u751a\u81f3\u80fd\u7528\u5927\u8111\u8ba1\u7b97\u51fa\u4e24\u4e2a\u5de8\u5927\u7684\u6570\u7684GCD\uff08\u6700\u5927\u516c\u7ea6
\u6570\uff09\uff01\u56e0\u6b64\u4ed6\u7ecf\u5e38\u548c\u522b\u4eba\u6bd4\u8d5b\u8ba1\u7b97GCD\u3002\u6709\u4e00\u5929Sheng bill\u5f88\u56a3\u5f20\u5730\u627e\u5230\u4e86\u4f60\uff0c\u5e76\u8981\u6c42\u548c\u4f60\u6bd4
\u8d5b\uff0c\u4f46\u662f\u8f93\u7ed9Sheng bill\u5c82\u4e0d\u662f\u5f88\u4e22\u8138\uff01\u6240\u4ee5\u4f60\u51b3\u5b9a\u5199\u4e00\u4e2a\u7a0b\u5e8f\u6765\u6559\u8bad\u4ed6\u3002 <\/p>\n

Input <\/strong><\/p>\n

\u5171\u4e24\u884c\uff1a
\u7b2c\u4e00\u884c\uff1a\u4e00\u4e2a\u6570A\u3002
\u7b2c\u4e8c\u884c\uff1a\u4e00\u4e2a\u6570B\u3002 <\/p>\n

Output <\/strong><\/p>\n

\u4e00\u884c\uff0c\u8868\u793aA\u548cB\u7684\u6700\u5927\u516c\u7ea6\u6570\u3002 <\/p>\n

Sample Input <\/strong><\/p>\n<\/p>\n

Sample Output <\/strong><\/p>\n<\/p>\n

Hint <\/strong><\/p>\n

\u5bf9\u4e8e20%\u7684\u6570\u636e\uff0c0 < A , B \u2264 10 ^ 18\u3002
\u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c0 < A , B \u2264 10 ^ 10000\u3002<\/p>\n

Source <\/strong><\/p>\n

Day1
\u603b\u7b97AC\u4e86\u8fd9\u9898\uff0c\u611f\u8c22GCD\u3002\u3002\u3002
\u7136\u540e\u662f\u7b97\u6cd5\u3002\u3002\u3002TMD\u516b\u4e2dOJ\u5c45\u7136\u6ca1\u6709Java\u3002\u3002\u3002\u3002\u53ea\u597d\u81ea\u5df1\u5199\u9ad8\u7cbe\u5ea6\uff0c\u7b97\u6cd5\u662f\u8fd9\u6837\u7684\u3002\u3002
\u8bbe\u8fd9\u4e24\u4e2a\u6570\u662fA\uff0cB
\u90a3\u4e48\u82e52|A\u548cB \uff08A\uff0cB\uff09=2\uff08A\/2,B\/2\uff09\u3002\u3002
\u82e52|A\u4e142\u4e0d\u6574\u9664B\uff0c (A,B)=(A\/2,B)..
\u82e5A\u548cB\u90fd\u662f\u5947\u6570\uff0c\u8bbeA<B\uff0c\uff08A,B\uff09=(A,B-A)…
\u5173\u952e\u662f\u4e00\u822c\u7684\u9ad8\u7cbe\u5ea6\u8d85\u65f6\u5f88\u4e25\u91cd\u554a\u3002\u3002
\u4e8e\u662f\u538b\u4f4d\uff0c\u6211\u538b\u4e8610\u4f4d\u3002\u3002\u7ed3\u679c\u56e0\u4e3aLong Long\u7684\u95ee\u9898WA\u4e86\u51e0\u6b21\u3002\u3002\u3002
\u7136\u540e\u628a\u6240\u6709\u76842\u653e\u5728\u4e00\u8d77\u4e58\u3002\u3002\u3002
\u5c31\u5f88\u5feb\u4e86\u3002\u3002\u3002
Orz\u3002sevenk\u795e\u725b\u3002\u3002
Code\uff1a<\/p>\n

#include<cstdio>#include<cstring>#include<iostream>#define Rep(i,n) for(int i=0;i<n;i++)using namespace std;typedef unsigned long long ull;const int maxn=10000+10,L=10;const ull m=1e10;char C[maxn+10];ull P[L];struct BigInt{ ull H[maxn\/L+1];int l; BigInt() { memset(H,0,sizeof(H));l=0; } void divide() { ull d=0; for(int i=l;i>=0;i–) { d*=m;d+=H[i]; H[i]=d\/2;d%=2; } while(l&&!H[l])l–; } int mod() { return H[0]%2; } void operator*=(int x) { ull d=0; for(int i=0;i<=l;i++) { d+=H[i]*x;H[i]=d%m; d\/=m; } while(d)H[++l]=d%m,d\/=m; } void operator-=(const BigInt&o) { ull d=0; for(int i=0;i<=l;i++) { H[i]-=d; if(H[i]<o.H[i])H[i]+=m,d=1; else d=0; H[i]-=o.H[i]; } while(l&&!H[l])l–; } void ReadIn() { memset(C,0,sizeof(C)); scanf("%s",C);int s=0;l=0;ull a=0; for(int i=strlen(C)-1;i>=0;i–) { a+=(C[i]-‘0’)*P[s++]; if(s==L)H[l++]=a,s=0,a=0; } if(!s)l–;else H[l]=a; } void Print() { printf("%I64d",H[l]); for(int i=l-1;i>=0;i–)printf("%010I64d",H[i]); } bool operator<(const BigInt&o)const { if(l!=o.l)return l<o.l; for(int i=l;i>=0;i–) { if(H[i]<o.H[i])return true; if(H[i]>o.H[i])return false; } } bool iszero()const{return l==0&&H[l]==0;}}A[2];int main(){ freopen("in","r",stdin); P[0]=1;Rep(i,L-1)P[i+1]=P[i]*10; A[0].ReadIn();A[1].ReadIn(); int a=0,b=1,c=0; while(true) { if(A[b]<A[a])a^=b^=a^=b; \/\/A[a].Print();printf(",");A[b].Print(); \/\/puts(""); if(A[a].iszero()) { while(c>=16)A[b]*=(1<<16),c-=16; while(c–)A[b]*=2; A[b].Print(); break; } int i=A[a].mod(),j=A[b].mod(); if(!i)A[a].divide(); if(!j)A[b].divide(); if(!i&&!j)c++; if(i&&j)A[b]-=A[a]; }}61254 <\/p>\n","protected":false},"excerpt":{"rendered":"

[SDOI2009]SuperGCD Time Limit:4000MS Memory Limit:65536KTotal Submit:34 Accepted:6 Case Time Limit:1000MS Description Sheng bill\u6709\u7740\u60ca\u4eba\u7684\u5fc3\u7b97\u80fd\u529b\uff0c\u751a\u81f3\u80fd\u7528\u5927\u8111\u8ba1\u7b97\u51fa\u4e24\u4e2a\u5de8\u5927\u7684\u6570\u7684GCD\uff08\u6700\u5927\u516c\u7ea6 \u6570\uff09\uff01\u56e0\u6b64\u4ed6\u7ecf\u5e38\u548c\u522b\u4eba\u6bd4\u8d5b\u8ba1\u7b97GCD\u3002\u6709\u4e00\u5929Sheng bill\u5f88\u56a3\u5f20\u5730\u627e\u5230\u4e86\u4f60\uff0c\u5e76\u8981\u6c42\u548c\u4f60\u6bd4 \u8d5b\uff0c\u4f46\u662f\u8f93\u7ed9Sheng bill\u5c82\u4e0d\u662f\u5f88\u4e22\u8138\uff01\u6240\u4ee5\u4f60\u51b3\u5b9a\u5199\u4e00\u4e2a\u7a0b\u5e8f\u6765\u6559\u8bad\u4ed6\u3002 Input \u5171\u4e24\u884c\uff1a \u7b2c\u4e00\u884c\uff1a\u4e00\u4e2a\u6570A\u3002 \u7b2c\u4e8c\u884c\uff1a\u4e00\u4e2a\u6570B\u3002 Output \u4e00\u884c\uff0c\u8868\u793aA\u548cB\u7684\u6700\u5927\u516c\u7ea6\u6570\u3002 Sample Input Sample Output Hint \u5bf9\u4e8e20%\u7684\u6570\u636e\uff0c0 < A , B \u2264 10 ^ 18\u3002 \u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c0 < A , B \u2264 10 ^ 10000\u3002 Source Day1\u603b\u7b97AC\u4e86\u8fd9\u9898\uff0c\u611f\u8c22GCD\u3002\u3002\u3002\u7136\u540e\u662f\u7b97\u6cd5\u3002\u3002\u3002TMD\u516b\u4e2dOJ\u5c45\u7136\u6ca1\u6709Java\u3002\u3002\u3002\u3002\u53ea\u597d\u81ea\u5df1\u5199\u9ad8\u7cbe\u5ea6\uff0c\u7b97\u6cd5\u662f\u8fd9\u6837\u7684\u3002\u3002\u8bbe\u8fd9\u4e24\u4e2a\u6570\u662fA\uff0cB\u90a3\u4e48\u82e52|A\u548cB \uff08A\uff0cB\uff09=2\uff08A\/2,B\/2\uff09\u3002\u3002\u82e52|A\u4e142\u4e0d\u6574\u9664B\uff0c (A,B)=(A\/2,B)..\u82e5A\u548cB\u90fd\u662f\u5947\u6570\uff0c\u8bbeA<B\uff0c\uff08A,B\uff09=(A,B-A)…\u5173\u952e\u662f\u4e00\u822c\u7684\u9ad8\u7cbe\u5ea6\u8d85\u65f6\u5f88\u4e25\u91cd\u554a\u3002\u3002\u4e8e\u662f\u538b\u4f4d\uff0c\u6211\u538b\u4e8610\u4f4d\u3002\u3002\u7ed3\u679c\u56e0\u4e3aLong Long\u7684\u95ee\u9898WA\u4e86\u51e0\u6b21\u3002\u3002\u3002\u7136\u540e\u628a\u6240\u6709\u76842\u653e\u5728\u4e00\u8d77\u4e58\u3002\u3002\u3002\u5c31\u5f88\u5feb\u4e86\u3002\u3002\u3002Orz\u3002sevenk\u795e\u725b\u3002\u3002Code\uff1a #include<cstdio>#include<cstring>#include<iostream>#define Rep(i,n) for(int i=0;i<n;i++)using […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/270"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=270"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/270\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=270"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=270"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=270"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}