-
-
Save meooow25/f890631681d50a94fef515fa9ac9ca1b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.InputStream; | |
class Fraction | |
{ | |
long num, den; | |
Fraction(long n, long d) | |
{ | |
num = n; den = d; | |
} | |
Fraction(double n, int places) | |
{ | |
num = (long)n; den = 1; n -= (long)n; | |
for(;places > 0; --places) | |
{ | |
n *= 10; num = (10 * num) + (long)n; n -= (long)n; | |
den *= 10; | |
} | |
} | |
long gcd(long a, long b) | |
{ | |
long temp; | |
a = Math.abs(a); b = Math.abs(b); | |
while(b > 0) | |
{ | |
temp = b; b = a % b; a = temp; | |
} | |
return a; | |
} | |
void reduce() | |
{ | |
long gcd = gcd(num, den); | |
num /= gcd; den /= gcd; | |
} | |
void add(Fraction f, long MOD) | |
{ | |
num = ((num * f.den) % MOD + (f.num * den) % MOD) % MOD; | |
den *= f.den; den %= MOD; | |
} | |
void multiply(Fraction f,long MOD) | |
{ | |
num *= f.num; num %= MOD; | |
den *= f.den; den %= MOD; | |
} | |
void invert() | |
{ | |
long temp = num; num = den; den = temp; | |
} | |
void negate() | |
{ | |
if(den < 0) den = -den; | |
else num = -num; | |
} | |
double decimalValue() | |
{ | |
return num / (double) den; | |
} | |
long modular_pow(long base, long exponent, long MOD) | |
{ | |
long result = 1; | |
while (exponent > 0) | |
{ | |
if (exponent % 2 == 1) | |
result = (result * base) % MOD; | |
exponent = exponent >> 1; | |
base = (base * base) % MOD; | |
} | |
return result; | |
} | |
void power(long exp, long MOD) | |
{ | |
num = modular_pow(num, exp, MOD); | |
den = modular_pow(den, exp, MOD); | |
} | |
long modInverse(long num, long MOD) | |
{ | |
return modular_pow(num, MOD - 2, MOD); | |
} | |
void print() | |
{ | |
System.out.println(num + " / " + den); | |
} | |
} | |
class StartHere | |
{ | |
static IO1 io = new IO1(System.in); | |
static final Fraction ONE = new Fraction(1l, 1l); | |
static final Fraction ONEi = new Fraction(-1l, 1l); | |
static final Fraction TWO = new Fraction(2l, 1l); | |
public static void main(String[] args) throws Exception | |
{ | |
for(int tc = io.nextInt(); tc > 0; --tc) | |
{ | |
Fraction fr = new Fraction(io.nextLong(), io.nextLong()); | |
fr.reduce(); | |
fr.add(ONEi, Long.MAX_VALUE); | |
if((fr.num < 0 && fr.den >= 0) || (fr.num >= 0 && fr.den < 0)) | |
fr.negate(); | |
fr.multiply(TWO, Long.MAX_VALUE); | |
fr.invert(); | |
fr.reduce(); | |
fr.multiply(new Fraction(io.nextLong()-1, 1l), Long.MAX_VALUE); | |
fr.reduce(); | |
long val = 1 + (long) fr.decimalValue(); | |
io.println(val); | |
} | |
io.flush(); | |
} | |
} | |
class IO1 | |
{ | |
static byte[] buf = new byte[2048]; | |
static int index, total; | |
static InputStream in; | |
static StringBuilder sb = new StringBuilder(); | |
IO1(InputStream is) | |
{ | |
in = is; | |
} | |
int scan() throws Exception | |
{ | |
if(index>=total){ | |
index = 0; | |
total = in.read(buf); | |
if(total<=0) | |
return -1; | |
} | |
return buf[index++]; | |
} | |
String next() throws Exception | |
{ | |
int c; | |
for(c=scan(); c<=32; c=scan()); | |
StringBuilder sb = new StringBuilder(); | |
for(; c>32; c=scan()) | |
sb.append((char)c); | |
return sb.toString(); | |
} | |
int nextInt() throws Exception | |
{ | |
int c, val = 0; | |
for(c=scan(); c<=32; c=scan()); | |
boolean neg = c=='-'; | |
if(c=='-' || c=='+') | |
c = scan(); | |
for(; c>='0' && c<='9'; c=scan()) | |
val = (val<<3) + (val<<1) + (c&15); | |
return neg?-val:val; | |
} | |
long nextLong() throws Exception | |
{ | |
int c;long val = 0; | |
for(c=scan(); c<=32; c=scan()); | |
boolean neg = c=='-'; | |
if(c=='-' || c=='+') | |
c = scan(); | |
for(; c>='0' && c<='9'; c=scan()) | |
val = (val<<3) + (val<<1) + (c&15); | |
return neg?-val:val; | |
} | |
void print(Object a) | |
{ | |
sb.append(a.toString()); | |
} | |
void println(Object a) | |
{ | |
sb.append(a.toString()).append("\n"); | |
} | |
void println() | |
{ | |
sb.append("\n"); | |
} | |
void flush() | |
{ | |
System.out.print(sb); | |
sb = new StringBuilder(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment