首页 > 代码库 > POJ 2115 C Looooops（模线性方程）
POJ 2115 C Looooops（模线性方程）
http://poj.org/problem?id=2115
题意：
给你一个变量，变量初始值a，终止值b，每循环一遍加c，问一共循环几遍终止，结果mod2^k.如果无法终止则输出FOREVER。
思路：
根据题意原题可化成c * x = b - a mod (2 ^ k)，然后解这个模线性方程。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 using namespace std;12 typedef long long ll;13 typedef pair<int,int> pll;14 const int INF=0x3f3f3f3f;15 const int maxn=1000+5;16 17 int a,b,c,k;18 19 void gcd(ll a,ll b,ll& d,ll& x,ll& y)20 {21 if(!b) {d=a;x=1;y=0;}22 else23 {24 gcd(b,a%b,d,y,x);25 y-=x*(a/b);26 }27 }28 29 ll modeq(ll a,ll b,ll n)30 {31 ll e,i,d,x,y,f;32 gcd(a,n,d,x,y);33 if(b%d) return -1;34 else35 {36 f=n/d<0?(-1*n/d):n/d;37 e=(x*(b/d)%f+f)%f;38 return e;39 }40 }41 42 int main()43 {44 //freopen("D:\\input.txt","r",stdin);45 while(~scanf("%d%d%d%d",&a,&b,&c,&k) && a+b+c+k!=0)46 {47 ll n=b-a;48 ll m=1LL<<k;49 ll ans = modeq(c,n,m);50 if(ans==-1) puts("FOREVER");51 else printf("%lld\n",ans);52 }53 return 0;54 }
POJ 2115 C Looooops（模线性方程）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。