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
last reply
- 1
reply
- 488
views
- 2
users
- 1
link