1 / 2
May 2021

link-----> https://www.spoj.com/problems/GCD2/5

#include<stdio.h>
#include<math.h>

long long int modpower(long long int a,long long int b,long int m)
{
if(b==0)
return 1;
long long int x=modpower(a,b/2,m);
x=(x * x)%m;
if(b & 1)
x=(x*a)%m;
return x;

}

long long unsigned int gcd(long long unsigned int b,long long unsigned int a)
{
if(a==0)
return b;
int k=b/10;
long long unsigned int u=pow(10,k);
int g=b%u;
if (k==0)
return gcd(a,b%a);

return gcd(a,((modpower(10,k,a)+g%a)%a));

}

int main()
{
int t;
long long unsigned int a[t],b[t];
scanf("%d",&t);
for(int i=0;i<t;i++)
{
{scanf("%llu %llu",&a[i],&b[i]);}

}

for(int i=0;i<t;i++)
{
{printf("%llu\n",gcd(b[i],a[i]) );}
}

}

  • created

    May '21
  • last reply

    May '21
  • 1

    reply

  • 488

    views

  • 2

    users

  • 1

    link