# HackerEarth GCD Strings problem solution

In this HackerEarth GCD Strings problem solution Let P[0...N-1] be a binary string of length N. Then let's define S to power infinite (P) as an infinite string with S to power infinite[i] = P[i % N] all I >= 0 (informally, S to power infinite (P) is the concatenation of P with itself an infinite number of times).

Define the GCD-string of two integers a,b, with a >= b to be a binary string of length a that satisfies the following:

g (a,b) = 100...000 (1 followed by a - 1 zeros ) if a is divisible by b
g(a,b) = First a characters of S to power infinite (g(b,a mod b)) otherwise
We can define F(a,b) to be the value of the integer represented by the binary string g(a,b) in base-2. Given T pairs of integers (x, y), compute F(x,y) mod 10 to power 9 plus 7 for each pair.

## HackerEarth GCD Strings problem solution.

`import java.io.OutputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.StringTokenizer;import java.io.IOException;import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.InputStream;public class Main {    public static void main(String[] args) {        InputStream inputStream = System.in;        OutputStream outputStream = System.out;        InputReader in = new InputReader(inputStream);        PrintWriter out = new PrintWriter(outputStream);        GCDStrings solver = new GCDStrings();        int testCount = Integer.parseInt(in.next());        for (int i = 1; i <= testCount; i++)            solver.solve(i, in, out);        out.close();    }    static class GCDStrings {        public int mod = 1000000007;        public void solve(int testNumber, InputReader in, PrintWriter out) {            int x = in.nextInt(), y = in.nextInt();            out.println(f(x, y)[0]);        }        public long pow(long b, long e) {            long r = 1;            while (e > 0) {                if (e % 2 == 1) r = r * b % mod;                b = b * b % mod;                e >>= 1;            }            return r;        }        public long sum(long shift, long terms) {            return (pow(2, shift * terms) + mod - 1) * pow(pow(2, shift) + mod - 1, mod - 2) % mod;        }        public long[] f(int x, int y) {            if (x % y == 0) return new long[]{pow(2, x - 1), pow(2, y - 1)};            long[] r = f(y, x % y);            return new long[]{((r[0] * sum(y, x / y) % mod * pow(2, x % y)) + r[1]) % mod, r[0]};        }    }    static class InputReader {        public BufferedReader reader;        public StringTokenizer tokenizer;        public InputReader(InputStream stream) {            reader = new BufferedReader(new InputStreamReader(stream), 32768);            tokenizer = null;        }        public String next() {            while (tokenizer == null || !tokenizer.hasMoreTokens()) {                try {                    tokenizer = new StringTokenizer(reader.readLine());                } catch (IOException e) {                    throw new RuntimeException(e);                }            }            return tokenizer.nextToken();        }        public int nextInt() {            return Integer.parseInt(next());        }    }}`

### Second solution

`#include<bits/stdc++.h>#include<iostream>using namespace std;#define fre     freopen("in.txt","r",stdin);freopen("0.out","w",stdout)#define abs(x) ((x)>0?(x):-(x))#define MOD 1000000007#define LL signed long long int#define scan(x) scanf("%d",&x)#define print(x) printf("%d\n",x)#define scanll(x) scanf("%lld",&x)#define printll(x) printf("%lld\n",x)#define rep(i,from,to) for(int i=(from);i <= (to); ++i)#define pii pair<int,int>LL pow(LL base, LL exponent,LL modulus = MOD){    LL result = 1;    while (exponent > 0)    {        if (exponent % 2 == 1)            result = (result * base) % modulus;        exponent = exponent >> 1;        base = (base * base) % modulus;    }    return result;}LL func(LL x,LL n, LL len){    LL r = pow(2,len,MOD);    LL temp = (pow(r, n, MOD)-1) * pow(r-1, MOD-2, MOD) % MOD;    temp = temp * x % MOD;    return temp;}pair<LL,LL> gcd(int a,int b){    if(a%b==0){        return {pow(2,a-1,MOD), pow(2,b-1,MOD)};    }    else{        pair<LL,LL> x = gcd(b, a%b);        return {(func(x.first,a/b,b) * pow(2,a%b,MOD) + x.second) % MOD, x.first};    }}int main(){    int T;    cin>>T;    while(T--){        int x,y;        cin>>x>>y;        cout<<gcd(x,y).first<<endl;    }}`