poj2115C Looooops 拓展欧几里德-白红宇的个人博客

发布日期：2021-06-29 05:37:45 浏览次数：2 分类：技术文章

本文共 1821 字，大约阅读时间需要 6 分钟。

C Looooops

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 27800		Accepted: 7915

Description

A Compiler Mystery: We are given a C-language style for loop of type

for (variable = A; variable != B; variable += C)  statement;

I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values 0 <= x < 2

^k) modulo 2

^k.

Input

The input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 <= k <= 32) is the number of bits of the control variable of the loop and A, B, C (0 <= A, B, C < 2

^k) are the parameters of the loop.

The input is finished by a line containing four zeros.

Output

The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate.

Sample Input

3 3 2 163 7 2 167 3 2 163 4 2 160 0 0 0

Sample Output

0232766FOREVER

题意：给定for循环

for (variable = A; variable != B; variable += C)

其中运算都是要模2^k，即variable每次都要模2^k。求一共要循环多少次。

解析：将这个循环可以整理成(A + x*C) % 2^k = B，进一步推得A + x*C = B + y*2^k，移项得x*C - y*2^k = B-A，即方程ax +by = c的形式，用拓展欧几里德解方程即可。

代码：

#include 
   
    typedef  long long ll;ll exgcd(ll a, ll b, ll &x, ll &y){	ll 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(){	ll A, B, C, K;	while(scanf("%lld%lld%lld%lld", &A, &B, &C, &K), (A+B+C+K)){		ll a = C;		ll b =(ll) 1<

转载地址：https://blog.csdn.net/zhj_fly/article/details/75759972 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：除法取模和逆元

下一篇：欧几里德与拓展欧几里德定理

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章