You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
20 lines
409 B
C++
20 lines
409 B
C++
#include <cstdio>
|
|
using namespace std;
|
|
typedef long long ll;
|
|
ll calc(ll a,ll b){return b==0?1:a/b+calc(b,a%b);}
|
|
int main()
|
|
{
|
|
int T,t=0;
|
|
scanf("%d",&T);
|
|
while(T--)
|
|
{
|
|
ll a,b,ans;
|
|
scanf("%lld%lld",&a,&b);
|
|
if((a|b)==0) ans=1;
|
|
else if((a&&b)==0) ans=2;
|
|
else ans=calc(a,b);
|
|
printf("Case #%d: %lld\n",++t,ans);
|
|
}
|
|
return 0;
|
|
}
|