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

题目链接:

Description

Given two integers A and B. Sequence S is defined as follow:

Input

The first 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 ≤ 10^18).

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

Problem solving:

找规律，模拟演算过程。例如a = S0 = 10, b = s1 = 3; 

#include 
   
    long long ans;void gcd(long long a, long long b){    if (!b)        return ;    ans += a / b;    gcd(b, a % b);}int main(){    int t;    long long a, b;    scanf("%d", &t);    for (int i = 1; i <= t; i++)    {        ans = 1;        scanf("%lld%lld", &a, &b);        if (!a && b || a && !b)            ans++;        gcd(a, b);        printf("Case #%d: %lld\n", i, ans);    }    return 0;}
   

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