房地产网站推荐,门户网站建设公司报价,创建网站的英语,广州番禺景点正题
链接#xff1a; http://poj.org/problem?id2115 大意
就是给出个循环 for(iA;i!B;i(iC)mod2k)for(iA;i!B;i(iC)mod2k)求需要循环次数 解题思路
我们定义l2kl2k首先可以推出#xff1a; CxA≡B(modl)CxA≡B(modl)然后解mod CxABlkCxABlk然后定义y−ly−l#xff0…正题
链接 http://poj.org/problem?id2115 大意
就是给出个循环
for(iA;i!B;i(iC)mod2k)for(iA;i!B;i(iC)mod2k)for (i=A;i!=B;i=(i+C)mod2^k)
求需要循环次数 解题思路
我们定义l2kl2kl=2^k 首先可以推出
CxA≡B(modl)CxA≡B(modl)Cx+A≡B(mod l)
然后解mod
CxABlkCxABlkCx+A=B+lk
然后定义y−ly−ly=-l移项
CxlyB−ACxlyB−ACx+ly=B-A
然后我们定义dgcd(C,l)dgcd(C,l)d=gcd(C,l)之后同时除去d
Cx/dly/d(A−B)/dCx/dly/d(A−B)/dCx/d+ly/d=(A-B)/d
因为d是C和l的最大公约数那么因为CCC%d=0" role="presentation" style="position: relative;">d=0d=0d=0,lll%d=0" role="presentation" style="position: relative;">d=0d=0d=0所以只要(A−B)(A−B)(A-B)%d0d0d=0这个方程就有解 之后因为这样求出的x不是最大解所以我们要 定义g(l/d)g(l/d)g=(l/d) 然后
(x∗((B−A)/d)(x∗((B−A)/d)(x*((B-A)/d)%gg)gg)g+g)%ggscript typemath/tex idMathJax-Element-28g/script
求出最小解 代码
#includecstdio
using namespace std;
long long x,y,d,a,b,c,k;
long long gcdup(long long a,long long b)
{if (b0){x1;y0;return a;}dgcdup(b,a%b);long long kx;xy;yk-a/b*y;return d;
}
int main()
{while (true){scanf(%lld%lld%lld%lld,a,b,c,k);if (a0 b0 c0 k0) break;k1llk;dgcdup(c,k);if ((b-a)%d) printf(FOREVER\n);else printf(%lld\n,(x*((b-a)/d)%(k/d)(k/d))%(k/d));}
}
