当前位置: 代码迷 >> 综合 >> POJ - 2115 C Looooops(拓展欧几里得,解同余方程)
  详细解决方案

POJ - 2115 C Looooops(拓展欧几里得,解同余方程)

热度:98   发布时间:2023-12-09 20:13:07.0

链接:POJ - 2115 C Looooops

题意:

一个C语言的for循环:

for(int i=A;i!=B;i+=C)st;

其中i表示变量, A A A B B B C C C分别表示初值、终值和步长, s t st st表示循环体。
要求计算当循环变量i运算在k位无符号整数体系下(运算值范围: 0 0 0 ~ 2 k ? 1 2^k-1 2k?1,此时, i i i+= C C C溢出后截断),循环体 s t st st会执行多少次?



分析:

设执行次数 x x x,那么根据题意,则有: A + x C ≡ B ( m o d 2 k ) A+xC\equiv B\pmod {2^k} A+xCB(mod2k)

即同余方程: x C ≡ B ? A ( m o d 2 k ) xC\equiv B-A\pmod {2^k} xCB?A(mod2k)

则同余方程可化为方程: x C = B ? A ? y ? 2 k              ( y ∈ Z ) xC=B-A-y\cdot2^k\;\;\;\;\;\;(y\in Z) xC=B?A?y?2k(yZ)

   ?    x C + y ? 2 k = B ? A \implies xC+y\cdot2^k=B-A ?xC+y?2k=B?A

化为: a x + b y = c ax+by=c ax+by=c,其中 a = C ,    b = 2 k ,    c = B ? A a=C,\;b=2^k,\;c=B-A a=C,b=2k,c=B?A

拓展欧几里得解方程即可,解得特解 x 0 x_0 x0?后,求得最小正整数解 x m i n = ( x 0 m o d    t + t ) m o d    t x_{min}=(x_0\mod t+t)\mod t xmin?=(x0?modt+t)modt
其中 t = b gcd ? ( a , b ) t=\frac{b}{\gcd(a,b)} t=gcd(a,b)b?



以下代码:

#include<cstdio>
#define LL long long
using namespace std;
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(b==0){
    x=1;y=0;d=a;}else{
    exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int main()
{
    LL A,B,C,k;LL a,b,c,d,x,y,t;while(scanf("%lld %lld %lld %lld",&A,&B,&C,&k)&&A+B+C+k){
    a=C;b=1LL<<k;c=B-A;exgcd(a,b,d,x,y);if(c%d!=0)printf("FOREVER\n");else{
    x=x*c/d;t=b/d;x=(x%t+t)%t;printf("%lld\n",x);}}return 0;
}