首页 > 代码库 > POJ 2115 C Looooops
POJ 2115 C Looooops
题目:http://poj.org/problem?id=2115
题意:对于C的for(i=A ; i!=B ;i +=C)循环语句,问在k位存储系统中循环几次才会结束。若在有限次内结束,则输出循环次数。否则输出死循环。
思路:这道题是一个扩展欧几里德算法的拓展,求单变元模线性方程 即:Cx=(B-A)(mod 2^k)
扩展欧几里得算法和单变元模线性方程(传送门) + 比较详细的博客
代码:
/* ID: wuqi9395@126.com PROG: LANG: C++ */ #include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> #define INF (1<<30) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, n) for (int i = 0; i < n; i++) #define debug puts("===============") #define eps (1e-6) typedef long long ll; using namespace std; ll extend_gcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1, y = 0; return a; } else { ll r = extend_gcd(b, a % b, y, x); y -= x * (a / b); return r; } } vector<ll> line_mod_equation(ll a, ll b, ll n) { ll x, y; ll d = extend_gcd(a, n, x, y); vector<ll> ans; ans.clear(); if (b % d == 0) { x = (x % n + n) % n; x %= (n / d); ans.push_back(x * (b / d) % (n / d)); //for (ll i = 1; i < d; i++) ans.push_back((ans[0] + i * n / d) % n); } return ans; } int main () { //freopen("2.txt", "w", stdout); ll a, b, c, k; while(scanf("%lld%lld%lld%lld", &a, &b, &c, &k) , a || b || c || k) { ll n = 1LL << k; ll p = ((b - a) % n + n) % n; vector<ll> ans = line_mod_equation(c, p, n); if (ans.size() == 0) puts("FOREVER"); else printf("%lld\n", ans[0]); } return 0; }
POJ 2115 C Looooops
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。