{"id":42,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/%e7%ae%80%e4%bb%8b%e6%89%a9%e5%b1%95%e6%ac%a7%e5%87%a0%e9%87%8c%e5%be%b7%e5%ae%9a%e7%90%86\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"%e7%ae%80%e4%bb%8b%e6%89%a9%e5%b1%95%e6%ac%a7%e5%87%a0%e9%87%8c%e5%be%b7%e5%ae%9a%e7%90%86","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/%e7%ae%80%e4%bb%8b%e6%89%a9%e5%b1%95%e6%ac%a7%e5%87%a0%e9%87%8c%e5%be%b7%e5%ae%9a%e7%90%86\/","title":{"rendered":"\u7b80\u4ecb\u6269\u5c55\u6b27\u51e0\u91cc\u5fb7\u5b9a\u7406"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

<\/a>\u6b27\u51e0\u91cc\u5fb7\u5b9a\u7406:<\/h5>\n

\u5bf9\u4e8e\u6574\u6570a,b\u6765\u8bf4\uff0cgcd(a, b)==gcd(b, a%b)==d(a\u4e0eb\u7684\u6700\u5927\u516c\u7ea6\u6570)\uff0c\u53c8\u79f0\u4e3a\u8f97\u8f6c\u76f8\u9664\u6cd5<\/p>\n

\u8bc1\u660e\uff1a<\/p>\n

\u56e0\u4e3aa\u662fd\u7684\u500d\u6570\uff0cb\u662fd\u7684\u500d\u6570\uff1b\u6240\u4ee5a%d=0\uff1b b%d=0\uff1b<\/p>\n

\u8bbek=a\/b\uff1br=a%b\uff1b\u5219 a=k*b+r\uff1b<\/p>\n

\u7531\u4e0a\u5f97\u51fa\uff1ar=a-k*b\uff1b<\/p>\n

\u56e0\u4e3aa\u548cb\u90fd\u662fd\u7684\u500d\u6570\uff0c\u6240\u4ee5(a-k*b)\u4e5f\u662fd\u7684\u500d\u6570\uff0c\u6240\u4ee5r\u4e5f\u662fd\u7684\u500d\u6570\uff1b<\/p>\n

\u6240\u4ee5gcd(a, b)==gcd(b, a%b)==d<\/p>\n

\u800c\u4e3a\u4ec0\u4e48\u8981\u8bc1\u660egcd(a, b)==gcd(b, a%b)==d\u8fd9\u4e2a\u5f0f\u5b50\u6210\u7acb\u5462\uff1f<\/p>\n

\u5176\u5b9e\u8bc1\u660egcd(a, b)==gcd(a, a%b)==d\u8fd9\u4e2a\u5f0f\u5b50\u6210\u7acb\u4e5f\u662f\u53ef\u4ee5\u7684\uff0c\u56e0\u4e3aa\u4e5f\u662fd\u7684\u500d\u6570\uff0c\u4f46\u662f\u5728\u8fdb\u884c\u9012\u5f52\u4e4b\u524d\u8981\u8fdb\u884c\u4e00\u6b65\u64cd\u4f5c\uff0c\u5c31\u662f\u5224\u65ada\u4e0eb\u7684\u5927\u5c0f\uff0c\u5982\u679cab,\u90a3\u4e48a%b\n

\u4e8b\u5b9e\u53d1\u73b0\u8bc1\u660egcd(a, b)==gcd(b, a%b)==d\u8fd9\u4e2a\u5f0f\u5b50\u4f1a\u7f29\u5c0f\u5904\u7406\u7684\u6570\u636e\u7684\u8303\u56f4\uff1b<\/p>\n

\u6b27\u51e0\u91cc\u5fb7\u5e94\u7528\uff1a<\/p>\n

\u7528\u6765\u6c42a\uff0cb\u7684\u6700\u5927\u516c\u7ea6\u6570\u3002<\/p>\n

\u4ee3\u7801\u5b9e\u73b0\uff1a<\/p>\n

int<\/span> gcd<\/span>(<\/span>int<\/span> a,<\/span>int<\/span> b)<\/span>\n{<\/span>\n    if<\/span>(<\/span>b==<\/span>0<\/span>)<\/span>\n        return<\/span> a;<\/span>\n    else<\/span>\n        return<\/span> gcd<\/span>(<\/span>b,<\/span>a%<\/span>b)<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n
<\/a>\u6269\u5c55\u6b27\u51e0\u91cc\u5fb7\u5b9a\u5f8b\uff1a<\/h5>\n
\u5bf9\u4e8e\u4e0d\u5b8c\u5168\u4e3a0\u7684\u975e\u8d1f\u6574\u6570a\uff0cb;gcd(a, b)\u8868\u793aa, b\u7684\u6700\u5927\u516c\u7ea6\u6570\uff0c\u5fc5\u5b9a\u5b58\u5728\u6574\u6570\u5bf9x\uff0cy\uff0c\u6ee1\u8db3a*x+b*y==gcd(a, b);<\/p>\n
\u8bc1\u660e\uff1a<\/p>\n
a*x1+b*y1=gcd(a, b);<\/p>\n
b*x2+(a%b)*y2=gcd(b, a%b);<\/p>\n
\u56e0\u4e3a\u7531\u6b27\u51e0\u91cc\u5fb7\u5b9a\u7406\u77e5\uff1agcd(a, b)==gcd(b, a%b)<\/p>\n
\u6240\u4ee5a*x1+b*y1=b*x2+(a%b)*y2; \u3000\u3000\u56e0\u4e3ar=a%b, r =a-k*b\u6240\u4ee5==><\/p>\n
a*x1+b*y1=b*x2+(a-k*b)*y2; \u3000\u3000\u56e0\u4e3ak=a\/b;\u6240\u4ee5\u3000==><\/p>\n
a*x1+b*y1=b*x2+(a-(a\/b)*b)*y2; \u3000\u3000\u5c55\u5f00\u5f97\u5230\u3000\u3000==><\/p>\n
a*x1+b*y1=b*x2+a*y2-b*(a\/b)*y2;\u3000\u3000\u8f6c\u6362\u5f97\u5230 ==><\/p>\n
a*x1+b*y1=a*y2+b*(x2-(a\/b)*y2);<\/p>\n
\u89c2\u5bdf\u4e0a\u5f0f\u53ef\u77e5 x1=y2, y1=x2-a\/b*y2;<\/p>\n
\u7531\u6b64\u53ef\u77e5x1\uff0cy1\u662f\u7531x2\uff0cy2\u5f97\u51fa\u6765\u7684\uff0c\u7531\u6b64\u7c7b\u63a8x2\uff0cy2\u662f\u7531x3\uff0cy3\u5f97\u51fa\u6765\u7684\uff0c<\/p>\n
\u90a3\u4ec0\u4e48\u65f6\u5019\u662f\u7ec8\u6b62\u5462\uff1f\u4e5f\u5c31\u662f\u9012\u5f52gcd(a, b)\u4e2db=0\u65f6\uff1b\u4e5f\u5c31\u662f\u8bf4\u6b64\u65f6a\u7684\u503c\u5c31\u662f\u8981\u6c42\u5f97\u6700\u5927\u516c\u7ea6\u6570<\/p>\n
\u5373gcd(a, 0)\u6b64\u65f6\u7531\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u5b9a\u5f8ba*x+b*y==gcd(a, b)\u77e5 a*x+b*y=a;<\/p>\n
\u89e3\u51fax=1, y=0;<\/p>\n
\u6b64\u65f6\u5c31\u662f\u9012\u5f52\u7ec8\u6b62\u7684\u5730\u65b9\uff1a<\/p>\n
\u6269\u5c55\u6b27\u51e0\u91cc\u5fb7\u5e94\u7528\uff1a<\/p>\n
\u5c31\u6211\u76ee\u524d\u6240\u77e5\u7684\u5c31\u662f\uff1a\u6c42\u89e3\u4e0d\u5b9a\u65b9\u7a0b\uff1b\u5982a*x+b*y=c; \u5df2\u77e5a, b, c\u7684\u503c\u6c42x\u548cy\u7684\u503c<\/p>\n
\u90a3\u4e48\u95ee\u9898\u6765\u4e86\uff0c\u5982\u4f55\u5c06\u6269\u5c55\u6b27\u51e0\u91cc\u5fb7\u5b9a\u5f8b\u5e94\u7528\u5728\u6c42\u89e3\u4e0d\u5b9a\u65b9\u7a0b\u5462\uff1f<\/p>\n
\u53ef\u4ee5\u8fd9\u6837\u8f6c\u5316 a*x+b*y=gcd(a, b)*c\/gcd(a, b);<\/p>\n
\u6700\u540e\u8f6c\u5316\u4e3a a*x\/(c\/gcd(a, b))+b*y\/(c\/gcd(a, b))=gcd(a, b); \u6700\u540e\u6c42\u51fa\u7684\u89e3x0\uff0cy0\u4e58\u4e0ac\/gcd(a, b)\u5c31\u662f\u6700\u7ec8\u7684\u7ed3\u679c\u4e86<\/p>\n
x1=x0*c\/gcd(a, b);<\/p>\n
y1=y0*c\/gcd(a, b);<\/p>\n
\u4ee3\u7801\u5b9e\u73b0\uff1a \u4e3e\u4f8b\u8bf4\u660e\uff1ahttp:\/\/codeforces.com\/problemset\/problem\/7\/C<\/p>\n
#include<\/span><\/span><\/span>\nlong<\/span> long<\/span> exgcd<\/span>(<\/span>long<\/span> long<\/span> a,<\/span> long<\/span> long<\/span> b,<\/span> long<\/span> long<\/span> &<\/span>x,<\/span> long<\/span> long<\/span> &<\/span>y)<\/span>;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    long<\/span> long<\/span> a,<\/span> b,<\/span> c,<\/span> ans,<\/span> x,<\/span> y;<\/span>\n \n    while<\/span>(<\/span>scanf<\/span>(<\/span>\"%lld%lld%lld\"<\/span>,<\/span> &<\/span>a,<\/span> &<\/span>b,<\/span> &<\/span>c)<\/span>!=<\/span>EOF<\/span>)<\/span>\n    {<\/span>\n        ans=<\/span>exgcd<\/span>(<\/span>a,<\/span> b,<\/span> x,<\/span> y)<\/span>;<\/span>\n        if<\/span>(<\/span>c%<\/span>ans==<\/span>0<\/span>)<\/span>\n        {<\/span>\n            x=<\/span>-<\/span>x*<\/span>c\/<\/span>ans;<\/span>\n            y=<\/span>-<\/span>y*<\/span>c\/<\/span>ans;<\/span>\n            printf<\/span>(<\/span>\"%lld %lldn\"<\/span>,<\/span> x,<\/span> y)<\/span>;<\/span>\n        }<\/span>\n        else<\/span>\n            printf<\/span>(<\/span>\"-1n\"<\/span>)<\/span>;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\nlong<\/span> long<\/span> exgcd<\/span>(<\/span>long<\/span> long<\/span> a,<\/span> long<\/span> long<\/span> b,<\/span> long<\/span> long<\/span> &<\/span>x,<\/span> long<\/span> long<\/span> &<\/span>y)<\/span>\n{<\/span>\n    if<\/span>(<\/span>b==<\/span>0<\/span>)<\/span>\n    {<\/span>\n        x=<\/span>1<\/span>;<\/span>\n        y=<\/span>0<\/span>;<\/span>\n        return<\/span> a;<\/span>\n    }<\/span>\n    long<\/span> long<\/span> r=<\/span>exgcd<\/span>(<\/span>b,<\/span> a%<\/span>b,<\/span> x,<\/span> y)<\/span>,<\/span> t;<\/span>\n    t=<\/span>x;<\/span>\n    x=<\/span>y;<\/span>\n    y=<\/span>t-<\/span>(<\/span>a\/<\/span>b)<\/span>*<\/span>y;<\/span>\n    return<\/span> r;<\/span>\n}<\/span>\n<\/code><\/pre>\n
\u4f46\u8fd9\u53ea\u662f\u6c42\u5f97\u4e86\u4e00\u7ec4\u89e3x1\uff0cy1<\/p>\n
\u5bf9\u4e8ex,y\u5bf9\u5e94\u7684\u89e3\u96c6\u662f\uff1a<\/p>\n
x=x1+b\/gcd(a, b)*t;<\/p>\n
y=y1-b\/gcd(a, b)*t;<\/p>\n
\u8bc1\u660e\uff1a<\/p>\n
a*x+b*y=d,d=gcd(a,b).<\/p>\n
\u63a8\u5bfc\uff1aa*x1+b*y1=a*x2+b*y2<\/p>\n
—->a*(x1-x2)=b*(y2-y1)<\/p>\n
—->a\/d*(x1-x2)=b\/d*(y2-y1)<\/p>\n
—->a\/d,b\/d\u4e92\u8d28<\/p>\n
—->x1-x2=k*(b\/d),y2-y1=k*(a\/d)<\/p>\n
—–>x=x0+b\/d*k,y=y0-a\/d*k,k\u4e3a\u4efb\u610f\u6574\u6570\u3002<\/p>\n
\u53c2\u8003\u4e8e\uff1a<\/p>\n
\u62d3\u5c55GCD\uff0c\u5982\u4f55\u7531\u4e00\u7ec4\u89e3\u63a8\u51fa\u591a\u7ec4\u89e3\uff1f<\/a><\/p>\n
—————————-\u5206\u5272\u7ebf———————————————-<\/p>\n
http:\/\/icpc.upc.edu.cn\/problem.php?cid=1437&pid=5<\/a><\/p>\n
<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n
\u4e24\u53ea\u9752\u86d9\u5728\u7f51\u4e0a\u76f8\u8bc6\u4e86\uff0c\u5b83\u4eec\u804a\u5f97\u5f88\u5f00\u5fc3\uff0c\u4e8e\u662f\u89c9\u5f97\u5f88\u6709\u5fc5\u8981\u89c1\u4e00\u9762\u3002\u5b83\u4eec\u5f88\u9ad8\u5174\u5730\u53d1\u73b0\u5b83\u4eec\u4f4f\u5728\u540c\u4e00\u6761\u7eac\u5ea6\u7ebf\u4e0a\uff0c\u4e8e\u662f\u5b83\u4eec\u7ea6\u5b9a\u5404\u81ea\u671d\u897f\u8df3\uff0c\u76f4\u5230\u78b0\u9762\u4e3a\u6b62\u3002\u53ef\u662f\u5b83\u4eec\u51fa\u53d1\u4e4b\u524d\u5fd8\u8bb0\u4e86\u4e00\u4ef6\u5f88\u91cd\u8981\u7684\u4e8b\u60c5\uff0c\u65e2\u6ca1\u6709\u95ee\u6e05\u695a\u5bf9\u65b9\u7684\u7279\u5f81\uff0c\u4e5f\u6ca1\u6709\u7ea6\u5b9a\u89c1\u9762\u7684\u5177\u4f53\u4f4d\u7f6e\u3002\u4e0d\u8fc7\u9752\u86d9\u4eec\u90fd\u662f\u5f88\u4e50\u89c2\u7684\uff0c\u5b83\u4eec\u89c9\u5f97\u53ea\u8981\u4e00\u76f4\u671d\u7740\u67d0\u4e2a\u65b9\u5411\u8df3\u4e0b\u53bb\uff0c\u603b\u80fd\u78b0\u5230\u5bf9\u65b9\u7684\u3002\u4f46\u662f\u9664\u975e\u8fd9\u4e24\u53ea\u9752\u86d9\u5728\u540c\u4e00\u65f6\u95f4\u8df3\u5230\u540c\u4e00\u70b9\u4e0a\uff0c\u4e0d\u7136\u662f\u6c38\u8fdc\u90fd\u4e0d\u53ef\u80fd\u78b0\u9762\u7684\u3002\u4e3a\u4e86\u5e2e\u52a9\u8fd9\u4e24\u53ea\u4e50\u89c2\u7684\u9752\u86d9\uff0c\u4f60\u88ab\u8981\u6c42\u5199\u4e00\u4e2a\u7a0b\u5e8f\u6765\u5224\u65ad\u8fd9\u4e24\u53ea\u9752\u86d9\u662f\u5426\u80fd\u591f\u78b0\u9762\uff0c\u4f1a\u5728\u4ec0\u4e48\u65f6\u5019\u78b0\u9762\u3002
 \u6211\u4eec\u628a\u8fd9\u4e24\u53ea\u9752\u86d9\u5206\u522b\u53eb\u505a\u9752\u86d9A\u548c\u9752\u86d9B\uff0c\u5e76\u4e14\u89c4\u5b9a\u7eac\u5ea6\u7ebf\u4e0a\u4e1c\u7ecf0\u5ea6\u5904\u4e3a\u539f\u70b9\uff0c\u7531\u4e1c\u5f80\u897f\u4e3a\u6b63\u65b9\u5411\uff0c\u5355\u4f4d\u957f\u5ea61\u7c73\uff0c\u8fd9\u6837\u6211\u4eec\u5c31\u5f97\u5230\u4e86\u4e00\u6761\u9996\u5c3e\u76f8\u63a5\u7684\u6570\u8f74\u3002\u8bbe\u9752\u86d9A\u7684\u51fa\u53d1\u70b9\u5750\u6807\u662fx\uff0c\u9752\u86d9B\u7684\u51fa\u53d1\u70b9\u5750\u6807\u662fy\u3002\u9752\u86d9A\u4e00\u6b21\u80fd\u8df3m\u7c73\uff0c\u9752\u86d9B\u4e00\u6b21\u80fd\u8df3n\u7c73\uff0c\u4e24\u53ea\u9752\u86d9\u8df3\u4e00\u6b21\u6240\u82b1\u8d39\u7684\u65f6\u95f4\u76f8\u540c\u3002\u7eac\u5ea6\u7ebf\u603b\u957fL\u7c73\u3002\u73b0\u5728\u8981\u4f60\u6c42\u51fa\u5b83\u4eec\u8df3\u4e86\u51e0\u6b21\u4ee5\u540e\u624d\u4f1a\u78b0\u9762\u3002<\/p>\n
<\/a>\u8f93\u5165<\/h5>\n
\u8f93\u5165\u53ea\u5305\u62ec\u4e00\u884c5\u4e2a\u6574\u6570x\uff0cy\uff0cm\uff0cn\uff0cL\uff0c\u5176\u4e2dx\u2260y < 2000000000\uff0c0 < m\u3001n < 2000000000\uff0c0 < L < 2100000000\u3002<\/p>\n
<\/a>\u8f93\u51fa<\/h5>\n
\u8f93\u51fa\u78b0\u9762\u6240\u9700\u8981\u7684\u8df3\u8dc3\u6b21\u6570\uff0c\u5982\u679c\u6c38\u8fdc\u4e0d\u53ef\u80fd\u78b0\u9762\u5219\u8f93\u51fa\u4e00\u884c”Impossible”<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
1 2 3 4 5\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
4\n<\/code><\/pre>\n
<\/a>\u89e3\u6790<\/h5>\n
\u8bbe\u4e24\u53ea\u9752\u86d9\u8df3\u4e86t\u6b65\uff0cA\u7684\u5750\u6807\u4e3ax+mt,B\u7684\u5750\u6807\u4e3ay+nt\uff0c\u4ed6\u4eec\u76f8\u9047\u7684\u65f6\u5019\u6ee1\u8db3x+mt-(y+nt) = pL(p\u8868\u793a\u4e24\u9752\u86d9\u8d70\u8fc7\u7684\u8def\u7a0b\u76f8\u5deep\u5708)
 \u79fb\u9879\u540e\uff1a(n-m)t+Lp=x-y<\/p>\n
#include<\/span> <\/span><\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nconst<\/span> ll N=<\/span>1e9<\/span>+<\/span>7<\/span>;<\/span>\nll exgcd<\/span>(<\/span>ll a,<\/span> ll b,<\/span> ll &<\/span>x,<\/span> ll &<\/span>y)<\/span>\n{<\/span>\n    if<\/span>(<\/span>b==<\/span>0<\/span>)<\/span>\n    {<\/span>\n        x=<\/span>1<\/span>;<\/span>\n        y=<\/span>0<\/span>;<\/span>\n        return<\/span> a;<\/span>\n    }<\/span>\n    ll d =<\/span> exgcd<\/span>(<\/span>b,<\/span> a%<\/span>b,<\/span> x,<\/span> y)<\/span>;<\/span>\n    ll t =<\/span> x;<\/span>\n    x =<\/span> y;<\/span>\n    y =<\/span> t-<\/span>(<\/span>a\/<\/span>b)<\/span>*<\/span>y;<\/span>\n    return<\/span> d;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    ll x,<\/span>y,<\/span>m,<\/span>n,<\/span>l;<\/span>\n    cin>><\/span>x>><\/span>y>><\/span>m>><\/span>n>><\/span>l;<\/span>\n    if<\/span>(<\/span>m==<\/span>n)<\/span>\n    {<\/span>\n        cout<<<\/span>\"Impossible\"<\/span><<<\/span>endl;<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    }<\/span>\n    ll x1=<\/span>0<\/span>,<\/span>y1=<\/span>0<\/span>,<\/span>a=<\/span>n-<\/span>m,<\/span>b=<\/span>l,<\/span>c=<\/span>x-<\/span>y;<\/span>\n    ll d=<\/span>exgcd<\/span>(<\/span>a,<\/span>b,<\/span>x1,<\/span>y1)<\/span>;<\/span>\n    if<\/span>(<\/span>c%<\/span>d!=<\/span>0<\/span>)<\/span>\n    {<\/span>\n        cout<<<\/span>\"Impossible\"<\/span><<<\/span>endl;<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    }<\/span>\n    else<\/span>\n    {<\/span>\n        x1=<\/span>x1*<\/span>c\/<\/span>d;<\/span>\n        x1=<\/span>(<\/span>x1%<\/span>(<\/span>b\/<\/span>d)<\/span>+<\/span>(<\/span>b\/<\/span>d)<\/span>)<\/span>%<\/span>(<\/span>b\/<\/span>d)<\/span>;<\/span>\n        cout<<<\/span>x1<<<\/span>endl;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n
<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n
DIDIDI often takes a shower in school public bathroom. DIDIDI must take a shower in B days after the previous one, or he will die. For routine maintenance, bathroom closes one day per A days. But DIDIDI is lazy, he hopes he can take a shower as less as possible. So he wants to find a stable period for arranging dates of shower. For example, DIDIDI should take a shower every 3-day, and bathroom closes every Sunday. In order to minimize the shower times, in every two-week, DIDIDI can choose Monday, Thursday, Saturday (to avoid Sunday), Tuesday, Friday to take shower. In this case, he need to take a shower 2.5 times per week. Your assignment is to calculate how many times per A days DIDIDI need to take a shower.<\/p>\n
<\/a>\u8f93\u5165<\/h5>\n
The first line of input contains a positive integer T telling you there are T test cases followed.
 Each test case will contain two integer, A, B.<\/p>\n
<\/a>\u8f93\u51fa<\/h5>\n
For each test case, print a line \u201cCase #x: y\u201d, where x is the case number (starting from 1) and y is times per A days of taking a shower. (if y is not a integer, please print fraction like \u201ca\/b\u201d, gcd(a,b) = 1)<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
2\n7 3\n7 4\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
Case #1: 5\/2\nCase #2: 2\n<\/code><\/pre>\n
<\/a>\u63d0\u793a<\/h5>\n
Tips:1\u2264T\u22642000,2\u2264A,B\u22641e8
 Case 1: if bathroom closes in 7th day every 7 days, he can take a shower in 1st,4th, 6th, 2nd,5th,1st, 4th, 6th, 2nd,5th \u2026\u2026 every period contains five shower times and two 7-day, so answer is 5\/2.
 Csse 2: if bathroom closes in 7th day every 7 days, he can take a shower in 3rd,6th, 3rd, 6th \u2026\u2026every period contains two shower times and a 7-day, so answer is 2.<\/p>\n
<\/a>\u89e3\u51b3<\/h5>\n
\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff1aa*x+b *y=gcd(a,b)<\/p>\n
\u5bf9\u4e8e\u8fd9\u4e2a\u9898\uff0cgcd==1\u7684\u65f6\u5019\u624d\u4f1a\u7528\u5230\u8fd9\u4e2a\u6765\u6c42x,y\u3002 \u4f46\u662f\u5f97\u51fa\u7684\u53ea\u6709\u5176\u4e2d\u4e00\u4e2a(x,y)\uff0c\u5176\u4e2d\u4e00\u4e2a\u4e3a\u8d1f\u6570\uff0c\u800c\u4e14\u9898\u76ee\u4e2d\u5fc5\u987b by – a<\/em>x == 1.\u516c\u5f0f\u5f97\u51fa\u6765\u7684\u53ef\u80fd\u662f -1.<\/p>\n
\u5f97\u4e0d\u51fa\u7b54\u6848\uff0c\u4e66\u4e2d\u5199\u5230\u6709\u591a\u7ec4\u89e3\uff0c\u89e3\u7b49\u4e8e x+ka\u2019 , y-kb\u2019 (a\u2019 = a \/ gcd(a,b) , b\u2019 = b \/ gcd(a,b) \uff0ck\u4e3a\u6574\u6570).<\/p>\n
\u4f46\u662f\uff0c \u53ea\u6709a>0\u624d\u4e0d\u7b26\u5408\u60c5\u51b5,a\u53ea\u80fd\u6bcf\u6b21\u51cfb\u3002<\/p>\n
#include<\/span> <\/span><\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nconst<\/span> ll N=<\/span>1e9<\/span>+<\/span>7<\/span>;<\/span>\nll gcd<\/span>(<\/span>ll a,<\/span>ll b)<\/span>\n{<\/span>\n    if<\/span>(<\/span>b==<\/span>0<\/span>)<\/span>\n        return<\/span> a;<\/span>\n    else<\/span>\n        return<\/span> gcd<\/span>(<\/span>b,<\/span>a%<\/span>b)<\/span>;<\/span>\n}<\/span>\nll exgcd<\/span>(<\/span>ll a,<\/span> ll b,<\/span> ll &<\/span>x,<\/span> ll &<\/span>y)<\/span>\n{<\/span>\n    if<\/span>(<\/span>b==<\/span>0<\/span>)<\/span>\n    {<\/span>\n        x=<\/span>1<\/span>;<\/span>\n        y=<\/span>0<\/span>;<\/span>\n        return<\/span> a;<\/span>\n    }<\/span>\n    ll d =<\/span> exgcd<\/span>(<\/span>b,<\/span> a%<\/span>b,<\/span> x,<\/span> y)<\/span>;<\/span>\n    ll t =<\/span> x;<\/span>\n    x =<\/span> y;<\/span>\n    y =<\/span> t-<\/span>(<\/span>a\/<\/span>b)<\/span>*<\/span>y;<\/span>\n    return<\/span> d;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> t;<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>t)<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> t1=<\/span>1<\/span>;<\/span>t1<=<\/span>t;<\/span>t1++<\/span>)<\/span>\n    {<\/span>\n        ll a,<\/span>b;<\/span>\n        scanf<\/span>(<\/span>\"%lld%lld\"<\/span>,<\/span>&<\/span>a,<\/span>&<\/span>b)<\/span>;<\/span>\n        ll g=<\/span>gcd<\/span>(<\/span>a,<\/span>b)<\/span>;<\/span>\n        if<\/span>(<\/span>g==<\/span>1<\/span>)<\/span>\n        {<\/span>\n            ll x=<\/span>0<\/span>,<\/span>y=<\/span>0<\/span>;<\/span>\n            ll d=<\/span>exgcd<\/span>(<\/span>a,<\/span>b,<\/span>x,<\/span>y)<\/span>;<\/span>\n            if<\/span>(<\/span>abs<\/span>(<\/span>a*<\/span>x)<\/span>-<\/span>abs<\/span>(<\/span>b*<\/span>y)<\/span><<\/span>0<\/span>)<\/span>\n            {<\/span>\n                x=<\/span>abs<\/span>(<\/span>x)<\/span>;<\/span>\n                y=<\/span>abs<\/span>(<\/span>y)<\/span>;<\/span>\n                if<\/span>(<\/span>x==<\/span>1<\/span>)<\/span>\n                    cout<<<\/span>\"Case #\"<\/span><<<\/span>t1<<<\/span>\": \"<\/span><<<\/span>y<<<\/span>endl;<\/span>\n                else<\/span>\n                    cout<<<\/span>\"Case #\"<\/span><<<\/span>t1<<<\/span>\": \"<\/span><<<\/span>y<<<\/span>\"\/\"<\/span><<<\/span>x<<<\/span>endl;<\/span>\n            }<\/span>\n            else<\/span>\n            {<\/span>\n                while<\/span>(<\/span>abs<\/span>(<\/span>a*<\/span>x)<\/span>-<\/span>abs<\/span>(<\/span>b*<\/span>y)<\/span>>=<\/span>0<\/span>)<\/span>\n                {<\/span>\n                    x=<\/span>x-<\/span>b\/<\/span>d;<\/span>\n                    y=<\/span>y+<\/span>a\/<\/span>d;<\/span>\n                }<\/span>\n                x=<\/span>abs<\/span>(<\/span>x)<\/span>;<\/span>\n                y=<\/span>abs<\/span>(<\/span>y)<\/span>;<\/span>\n                if<\/span>(<\/span>x==<\/span>1<\/span>)<\/span>\n                    cout<<<\/span>\"Case #\"<\/span><<<\/span>t1<<<\/span>\": \"<\/span><<<\/span>y<<<\/span>endl;<\/span>\n                else<\/span>\n                    cout<<<\/span>\"Case #\"<\/span><<<\/span>t1<<<\/span>\": \"<\/span><<<\/span>y<<<\/span>\"\/\"<\/span><<<\/span>x<<<\/span>endl;<\/span>\n            }<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span>\n            if<\/span>(<\/span>b==<\/span>g)<\/span>\n            {<\/span>\n                cout<<<\/span>\"Case #\"<\/span><<<\/span>t1<<<\/span>\": \"<\/span><<<\/span>a\/<\/span>g<<<\/span>endl;<\/span>\n            }<\/span>\n            else<\/span>\n            {<\/span>\n                cout<<<\/span>\"Case #\"<\/span><<<\/span>t1<<<\/span>\": \"<\/span><<<\/span>a\/<\/span>g<<<\/span>\"\/\"<\/span><<<\/span>b\/<\/span>g<<<\/span>endl;<\/span>\n            }<\/span>\n        }<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u6b27\u51e0\u91cc\u5fb7\u5b9a\u7406: \u5bf9\u4e8e\u6574\u6570a,b\u6765\u8bf4\uff0cgcd(a, …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-42","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/42","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=42"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/42\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=42"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=42"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=42"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
http:\/\/icpc.upc.edu.cn\/problem.php?cid=2592&pid=2<\/a><\/p>\n
\u6b27\u51e0\u91cc\u5fb7\u548c\u6269\u5c55\u6b27\u51e0\u91cc\u5fb7\u8be6\u89e3 \u4ee5\u53ca\u4f8b\u9898CodeForces 7C<\/a><\/p>\n