#include <iostream>
#include <fstream>
#include <vector>
typedef int signed long long isll;
isll const minn = 1LL;
isll const maxn = 12000000000LL;
isll const minp = 1LL;
isll const maxp = 100000000000000LL; // 10 ** 14
// 1 <= n <= 12,000,000,000 (12 miliarde)
bool
square_root1(isll n, isll & sr)
{ bool ok; ok = ((minn<=n)&&(n<=maxn)); if(!ok) { return ok; }
isll p; isll q; isll r; p = 1; while((p*p)<=n) { p <<= 1; } p >>= 1;
for(q = p >> 1; 0<q; q >>= 1) { r = (p+q); if((r*r)<=n) { p = r; } }
sr = p; return true;
}
// 1 <= n <= 12,000,000,000 (12 miliarde)
bool
square_root2(isll n, isll & sr)
{ bool ok; ok = ((minn<=n) && (n<=maxn)); if(!ok) { return ok; }
isll p; isll q; isll r; q = n; q >>= 2; p = 1; while(0<q) { q >>= 2; p <<= 1; }
for(q = p >> 1; 0<q; q >>= 1) { r=(p+q); if((r*r)<=n) { p = r; } }
sr = p; return true;
}
bool
square_root_unit_test1()
{ isll n; isll n2; isll r1; isll r2; bool ok;
n=minn; n2 = n*n; while(n2<=maxn)
{ ok = square_root1(n2, r1); if(!ok) { return ok; }
ok = square_root2(n2, r2); if(!ok) { return ok; }
ok = ((n==r1)&&(n==r2)&&((r1*r1)<=n2)&&(n2<=((r1+1)*(r1+1)))); if(!ok) { return ok; }
++n; n2 = n*n;
}
return true;
}
bool
square_root_unit_test2()
{ isll n; isll n2; isll r1; isll r2; bool ok;
n = minn; n2=((n+1)*(n+1))-1; while(n2<=maxn)
{ ok = square_root1(n2, r1); if(!ok) { return ok; }
ok = square_root2(n2, r2); if(!ok) { return ok; }
ok = ((n==r1)&&(n==r2)&&((r1*r1)<=n2)&&(n2<=((r1+1)*(r1+1)))); if(!ok) { return ok; }
++n; n2 = ((n+1)*(n+1))-1;
}
return true;
}
bool
gcd(isll a, isll b, isll & cmmdc)
{ bool ok; ok = ((0<a)&&(0<b)); if(!ok) { return ok; }
isll r;
while(0!=b)
{ r = a%b;
a = b;
b = r;
}
// no - throw
cmmdc = a; return true;
}
class frac
{ private:
isll a_n;
isll a_p;
std::vector<isll> a_prime_factors;
std::vector<isll> a_prime_factors_correct;
int a_number_of_coprimes;
int a_number_of_coprimes_correct;
isll a_ans;
isll a_ans_correct;
bool a_ok;
bool count_correct(isll a, isll b, isll & number);
bool count(isll a, isll b, isll & number);
bool find_prime_factors_of_n_correct();
bool find_prime_factors_of_n();
bool solve_correct();
bool solve();
bool write();
bool read();
bool run_unit_test3();
bool run_unit_test2();
bool run_unit_test1();
bool run_unit_tests();
bool process();
public:
class solver__use_case {};
class self_test__use_case {};
frac(solver__use_case & uc);
frac(self_test__use_case & uc);
bool get_ok() const throw();
};
bool
frac::get_ok() const throw()
{ return a_ok; }
frac::frac(solver__use_case & uc)
: a_ok(process())
{ (void)uc; }
frac::frac(self_test__use_case & uc)
: a_ok (run_unit_tests())
{ }
bool
frac::process()
{ bool ok; ok = read() &&
solve() &&
write();
return ok;
}
bool
frac::run_unit_test1()
{ std::cout << "find prime factors of n - unit test : ";
bool ok;
for(a_n=1; 10000>a_n; ++a_n)
{ ok = find_prime_factors_of_n(); if(!ok) { return ok; }
ok = find_prime_factors_of_n_correct(); if(!ok) { return ok; }
ok = (a_prime_factors == a_prime_factors_correct); if(!ok) { return ok; }
}
std::cout << "ok" << std::endl;
return true;
}
bool
frac::run_unit_test2()
{ bool ok;
std::cout << "count unit test 1: ";
std::vector<isll> primes1; primes1.push_back(2); primes1.push_back(3); primes1.push_back(5);
a_prime_factors.swap(primes1);
a_n = 2*3*5;
isll a; isll b; isll no1; isll no2;
for(a=1; 1000>a; ++a)
{ b = a+20;
ok = count(a, b, no1); if(!ok) { return ok; }
ok = count_correct(a, b, no2); if(!ok) { return ok; }
ok = (no1 == no2); if(!ok) { return ok; }
b = a+5000;
ok = count(a, b, no1); if(!ok) { return ok; }
ok = count_correct(a, b, no2); if(!ok) { return ok; }
ok = (no1 == no2); if(!ok) { return ok; }
}
std::cout<<"ok"<<std::endl;
std::cout << "count unit test 2: ";
std::vector<isll> primes2; primes2.push_back(2); primes2.push_back(3); primes2.push_back(5);
primes2.push_back(7); primes2.push_back(11); primes2.push_back(13);
a_prime_factors.swap(primes2);
a_n = 2*3*5*7*11*13;
for(a=1; 500>a; ++a)
{ b = a+2000;
ok = count(a, b, no1); if(!ok) { return ok; }
ok = count_correct(a, b, no2); if(!ok) { return ok; }
ok = (no1 == no2); if(!ok) { return ok; }
b = a+15000;
ok = count(a, b, no1); if(!ok) { return ok; }
ok = count_correct(a, b, no2); if(!ok) { return ok; }
ok = (no1 == no2); if(!ok) { return ok; }
}
std::cout << "ok" << std::endl;
return true;
}
bool
frac::run_unit_test3()
{ // + x x x + x n = 6, p = 2, ans = 5
// 1 2 3 4 5 6
bool ok;
std::cout<<"solve unit test 1 : ";
a_n = 6; a_p = 2;
ok = solve(); if(!ok) { return ok; }
ok = solve_correct(); if(!ok) { return ok; }
ok = (a_ans == a_ans_correct); if(!ok) { return ok; }
std::cout << "ok" << std::endl;
std::cout << "solve unit test 2 : ";
for(a_n = 1000; 5000>a_n; ++a_n)
{ a_p = 400;
ok = solve(); if(!ok) { return ok; }
ok = solve_correct(); if(!ok) { return ok; }
ok = (a_ans == a_ans_correct); if(!ok) { return ok; }
a_p = 11000;
ok = solve(); if(!ok) { return ok; }
ok = solve_correct(); if(!ok) { return ok; }
ok = (a_ans == a_ans_correct); if(!ok) { return ok; }
}
std::cout<<"ok"<<std::endl;
return true;
}
bool
frac::run_unit_tests()
{ bool ok; ok = run_unit_test1() &&
run_unit_test2() &&
run_unit_test3();
return ok;
}
bool
frac::read()
{ std::ifstream is("frac.in");
isll n; isll p; is >> n >> p;
bool ok; ok = ((minn<=n)&&(n<=maxn)) &&
((minp<=p)&&(p<=maxp)) &&
(!is.fail());
if(!ok) { return ok; }
a_n = n; a_p = p; return true;
}
bool
frac::write()
{ std::ofstream os("frac.out");
os << a_ans << std::endl;
bool ok; ok = os.good(); if(!ok) { return ok; }
os.close(); ok = os.good(); return ok;
}
bool
frac::solve()
{ bool ok; ok = find_prime_factors_of_n(); if(!ok) { return ok; }
isll n; n = a_n; isll cmul; ok = count(1, n, cmul); if(!ok) { return ok; }
isll ccop; ccop = ((n-1+1)-cmul); // count of numbers in set {1,...,n} that are coprime with n
isll p; p = a_p; isll k; k = (p-1) / ccop; p = p % ccop; if(0==p) { p = ccop; }
isll a; isll b; a = 1; b = n; isll m;
while(a<b)
{ m = (a+b)/2; ok = count(a, m, cmul); if(!ok) { return ok; }
ccop = (m-a+1)-cmul; if(p<=ccop) { b = m; } else { p -= ccop; a = m+1; }
}
if(1==p)
{ isll d;
ok = gcd(a, n, d); if(!ok) { return ok; }
ok = (1==d); if(!ok) { return ok; }
-- p;
}
ok = (0 == p); if(!ok) { return ok; }
ok = (b==a); if(!ok) { return ok; }
// no-throw
a_ans = (k * n) + b; return true;
}
bool
frac::solve_correct()
{ isll n; n = a_n; isll p; p = a_p;
isll i; isll d; bool ok;
for(i=1; true; ++i)
{ ok = gcd(i, n, d);
if(1==d)
{ --p; if(0==p) { a_ans_correct = i; return true; } }
}
return false;
}
bool
frac::find_prime_factors_of_n()
{ isll n; n = a_n; isll n1; n1 = n;
std::vector<isll> v;
if(0 == (n&1))
{ v.push_back(2); do { n >>= 1; } while (0==(n&1)); }
bool ok; isll r; ok = square_root2(n, r); if(!ok) { return ok; }
ok = ((0<=r)&&(((r*r)<=n)&&(n<((r+1)*(r+1))))); if(!ok) { return ok; }
isll f; f=3;
while(r>=f)
{ if(0==(n%f))
{ v.push_back(f); do { n /= f; } while (0 == (n%f));
ok = square_root2(n, r); if(!ok) { return ok; }
ok = ((0<=r)&&(((r*r)<=n)&&(n<((r+1)*(r+1))))); if(!ok) { return ok; }
}
f += 2;
}
if(1<n)
{ v.push_back(n); }
// no-throw
a_prime_factors.swap(v); return true;
}
bool
frac::find_prime_factors_of_n_correct()
{ isll n; n = a_n; isll i; i = 1;
std::vector<isll> v;
while(1!=n)
{ ++i;
if(0 == (n%i))
{ v.push_back(i);
do { n /= i; } while (0==(n%i));
}
}
// no-throw
a_prime_factors_correct.swap(v); return true;
}
bool
frac::count(isll a, isll b, isll & number)
{ std::vector<isll> prime((1<<a_prime_factors.size()), 0);
std::vector<isll> prod((1<<a_prime_factors.size()), 0);
std::vector<isll>::size_type i1;
std::vector<isll>::size_type i2; i2 = a_prime_factors.size();
for(i1=0; i2>i1; ++i1)
{ prime[(1<<i1)] = a_prime_factors[i1]; }
prod[0] = -1;
std::vector<isll>::size_type t; t = prod.size();
std::vector<isll>::size_type s; isll sum; sum = 0; isll inc;
std::vector<isll>::size_type e; isll p; isll x0; isll x; isll a1; isll b1;
for(s=1; t>s; ++s)
{ e = s&(-s); // compute lsb of s
p = prime[e]; x0 = -p * prod[s^e];
prod[s] = x0; if(0>x0) { x= -x0; } else { x = x0; }
a1 = a%x; if(0==a1) { a1 = a; } else { a1 = a+(x-a1); }
b1 = b%x; if(0==b1) { b1 = b; } else { b1 = b-b1; }
if(a1<=b1)
{ inc= 1+(b1-a1)/x;
if (0<x0) { sum += inc; }
else { sum -= inc; }
}
}
// no-throw
number = sum; return true;
}
bool
frac::count_correct(isll a, isll b, isll & number)
{ bool ok; ok = ((minn<=a) && (a<=b) && (b<=maxn)); if(!ok) { return ok; }
isll n; n = a_n; isll i; isll d; isll sum; sum = 0;
for(i=a; b>=i; ++i)
{ ok = gcd(i, n, d); if(!ok) { return ok; }
if(1<d) { ++sum; }
}
// no - throw
number = sum; return true;
}
bool
solve_frac()
{ frac::solver__use_case uc;
frac f(uc);
bool ok; ok = f.get_ok();
return ok;
}
bool
run_unit_tests()
{ bool ok;
std::cout << "square root unit test 1 : ";
ok = square_root_unit_test1(); if(!ok) { return ok; }
std::cout << "ok" << std::endl;
std::cout << "square root unit test 2 : ";
ok = square_root_unit_test2(); if(!ok) { return ok; }
std::cout << "ok" << std::endl;
frac::self_test__use_case uc; frac f(uc); ok = f.get_ok(); if(!ok) { return ok; }
return true;
}
bool
solve(int argc)
{ if(1==argc)
{ return solve_frac(); }
return run_unit_tests();
}
int
main(int argc, char * * argv)
{ int status;
bool ok;
try
{ ok = solve(argc);
status = ( ok ? 0 : 1 );
}
catch ( ... )
{ status = 2; }
return status;
}