POJ-----C Looooops
6442 단어 oop
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 15282
Accepted: 3893
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 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
Sample Output
0
2
32766
FOREVER
Source
CTU Open 2004
주소:
http://poj.org/problem?id=2115
유클리드 확장
변환 하 는 식 은 c * x + d * y = (b - a) mod (d) 입 니 다. d = 1LL < k (제목 의 뜻);
코드:
1 #include<iostream>
2 #include<cstdio>
3 #define LL long long
4 #include<cstring>
5 using namespace std;
6 LL x,y,q;
7 void exgcd(LL a, LL b)
8 {
9 if(b==0)
10 {
11 x=1,y=0,q=a;
12 }
13 else
14 {
15 exgcd(b,a%b);
16 LL temp=x;
17 x=y,y=temp-a/b*y;
18 }
19 }
20
21 int main()
22 {
23 LL a,b,c,k;
24 //freopen("test.in","r",stdin);
25 //freopen("test.out","w",stdout);
26 while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&k),a+b+c+k)
27 {
28 LL temp=(LL)1<<k;
29 exgcd(c,temp);
30 if((b-a)%q)
31 printf("FOREVER
");
32 else
33 {
34 LL t=temp/q;
35 printf("%I64d
",(x*((b-a)/q)%t+t)%t);
36 }
37 }
38 return 0;
39 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
핸들러 - 작은 구현이 좋은 이유는 무엇입니까?핸들러는 단순히 입력을 받아들이고, 가능한 경우 수신된 입력 데이터로 진행할지 선택적으로 결정하고, 입력을 적절한 형식으로 변환하고, 기본 프로시저를 호출합니다. 사용자/클라이언트는 사용자 인터페이스나 REST, 메...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.