Header Ad

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


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;
}
}

Post a Comment

0 Comments