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("%dn",x)
#define scanll(x) scanf("%lld",&x)
#define printll(x) printf("%lldn",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;
    }
}

coding problems