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
< 2k) 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 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
Sample Output
0
2
32766
FOREVER
题意:属于求解模线性方程的题,cx-y*2k=b-a
AC代码:
#include<iostream>
#include<string.h>
#include<string>
#include<cstdio>
#define N 11
using namespace std;
typedef long long L;
L d;
void gcd(L a,L b,L &x1,L &y1)
{
if(!b) {x1=1;y1=0;d=a;}
else
{
gcd(b,a%b,x1,y1);
int temp=x1;
x1=y1;
y1=temp-a/b*x1;
}
}
int main()
{
L a,b,c,k;
while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&k),a,b,c,k)
{
L a1=c;
L b1=(L)1<<k;//以2为底的幂运算可以由位运算来解决
L c1=b-a;
L x1,y1;
gcd(a1,b1,x1,y1);
L r=b1/d;
if(c1%d) printf("FOREVER\n");
else printf("%lld\n",(c1/d*x1%r+r)%r);
}return 0;
}
分享到:
相关推荐
北大POJ3414-Pots 解题报告+AC代码
poj3045的源码,很久以前写的,语言是C++
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
poj2880 输入一个英文句子,长度不超过40个字符。编写程序,输出句子中最长的一个单词。 http://poj.grids.cn/problem?id=2880 可直接运行
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
NULL 博文链接:https://128kj.iteye.com/blog/1754170
具体题目参考: http://poj.org/userstatus?user_id=tanzhangwen 本压缩文件里面有所有已经Accepted的题目的源码,主要语言为c/c++,少量java
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
POJ 是“北京大学程序在线评测系统”(Peking University Online Judge)的缩写,是个提供编程题目的网站,兼容Pascal、C、C++、Java、Fortran、Python等多种语言。 “北京大学程序在线评测系统”是一个免费的公益...
几个程序设计的训练网站给大家,供大家参考! http://poj.org/ 北大的,比较难 http://acm.hdu.edu.cn/ 杭电的,相对容易 http://cm2prod.baylor.edu/welcome.icpc ACM/ICPC官方网站
网上整理的一些poj刷题指南。 poj地址:http://poj.org
http://poj.org Sphere Online Judge-允许使用各种各样的编程语言【SPOJ】 http://www.spoj.pl/ SGU Online Contester-具有模拟参加历史比赛的虚拟赛功能 http://acm.sgu.ru/ Codeforces-不断维护历届题库 ...
POJ3273 Monthly Expense题解 题目分析: 给出N个数,要求你合并连续的数,使其合并在满足不差过M个合并后的集合的时候,不超过M个集合的和的最大值最小。
poj是http://poj.org/ vijos指https://vijos.org/ nowcoder指nowcoder.com,牛客网 vjudge指https://vjudge.net/,里面主要存codeforces.com和uva等外国网站的题,还有部分poj的题 luogu是指https://www.luogu.org/, 这...
NULL 博文链接:https://taojianrong.iteye.com/blog/1756785
//http://poj.org/problem?id=1611 #include using namespace std; const int maxn = 30010; int f[maxn],num[maxn],n,m; int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } int main() { while(cin...
http://poj.org/ 的离线版,收集了所有题目,无需联网即可用。
NULL 博文链接:https://200830740306.iteye.com/blog/603488
NULL 博文链接:https://200830740306.iteye.com/blog/603493