首页 > 代码库 > POJ 2115 C Looooops（Exgcd）
POJ 2115 C Looooops（Exgcd）
【题目链接】 http://poj.org/problem?id=2115
【题目大意】
求for (variable = A; variable != B; variable += C)的循环次数，
其中变量为k比特无符号整数。
【题解】
题目等价于求解Cx=(B–A)(mod 2^k)，利用扩展欧几里得算法可以求解该问题
【代码】
#include <algorithm>#include <cstring>#include <cstdio>using namespace std;typedef long long ll;ll exgcd(ll a,ll b,ll&x,ll&y){ if(!b)return x=1,y=0,a; ll d=exgcd(b,a%b,x,y),t=x; return x=y,y=t-a/b*y,d;}ll A,B,C,k;int main(){ while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k),A+B+C+k){ ll a=C,b=B-A,n=1LL<<k,x,y,d=exgcd(a,n,x,y); if(b%d)puts("FOREVER"); else{ x=(x*(b/d))%n; //方程ax=b(mod n)的最小解 x=(x%(n/d)+n/d)%(n/d); //方程ax=b(mod n)的最小整数解 printf("%I64d\n",x); } }return 0;}
POJ 2115 C Looooops（Exgcd）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。