Last Defence （2014 西安现场赛）

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=94237#problem/K

Last Defence

Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu

Given two integers A and B. Sequence S is deﬁned as follow:
• S0 = A
• S1 = B
• Si = |Si−1 − Si−2| for i ≥ 2
Count the number of distinct numbers in S.
Input
The ﬁrst line of the input gives the number of test cases, T. T test cases follow. T is about 100000.
Each test case consists of one line — two space-separated integers A, B. (0 ≤ A, B ≤ 1018).
Output
For each test case, output one line containing ‘Case #x: y’, where x is the test case number (starting
from 1) and y is the number of distinct numbers in S.
Sample Input
2
7 4
3 5
Sample Output
Case #1: 6
Case #2: 5

#include<stdio.h>

int main()

{

    long long t, iCase=;

    scanf("%lld", &t);

    while(t--)

    {

        long long a, b, sum=, k, t;

        scanf("%lld%lld", &a, &b);

        if(a<b)

          t=a, a=b, b=t;

        if(a== && b==)

        {

            printf("Case #%lld: 1\n", iCase++);

            continue;

        }

        else if(b==)

        {

            printf("Case #%lld: 2\n", iCase++);

            continue;

        }

        while(a%b!=)

        {

            sum += a/b;

            k = a;

            a = b;

            b = k%b;

        }

        sum += a/b;

        printf("Case #%lld: %lld\n", iCase++, sum+);

    }

    return ;

}

巴特西

Last Defence （2014 西安现场赛）

最新文章

热门文章