首页 > 代码库 > poj 2115 C Looooops (解模线性方程)
poj 2115 C Looooops (解模线性方程)
链接:poj 2115
题意:对于C语言的循环语句for(i=A ; i!=B ;i +=C),
问在k位存储系统中循环几次才会结束。
若在有限次内结束,则输出循环次数,否则输出死循环。
注:利用了 k位存储系统的数据特性进行循环(会溢出)
例如int型是16位的,那么int能保存2^16个数据,
即最大数为65535(本题默认为无符号),
当循环使得i超过65535时,则i会返回0重新开始计数
如i=65534,当i+=3时,i=1 即 i=(65534+3)%(2^16)=1
分析:设对于某组数据要循环x次结束,可得方程:
x=[(B-A+2^k)%2^k]/C
即 Cx=(B-A)(mod 2^k) 此方程为 模线性方程,本题就是求x的值。
即求模线性方程 ax=b mod n的解。 其中a=C,b=B-A,n=2^K.
该方程有解的充要条件为 gcd(a,n) | b ,即 b% gcd(a,n)==0
令d=gcd(a,n)有该方程的 最小整数解为 x0 = X (mod n/d)
X为任意解,x0为最小整数解
#include<stdio.h> __int64 exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y) //扩展欧几里得 { __int64 t,d; if(b==0){ x=1; y=0; return a; } d=exgcd(b,a%b,x,y); t=x; x=y; y=t-a/b*y; return d; } int main() { __int64 A,B,C,k,a,b,n,d,x,y; while(scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&k)!=EOF){ if(A==0&&B==0&&C==0&&k==0) break; a=C; b=B-A; n=(__int64)1<<k; //1要转化为64位 d=exgcd(a,n,x,y); if(b%d){ //若方程无解,则会一直循环 printf("FOREVER\n"); continue; } x=x*(b/d)%n; x=(x%(n/d)+(n/d))%(n/d); //求最小正解 printf("%I64d\n",x); } return 0; }
poj 2115 C Looooops (解模线性方程)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。