Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2864818)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll nmax = 110000;
const int pmax = 61;
int prime[nmax+5];
int primeNr;
int fct[nmax+5];
int fctNr;
bool c[nmax+5];
void sieve() {
for(int i=3; i*i<=nmax; i+=2)
if(!c[i])
for(int j=i*i; j<=nmax; j+=i)
c[j] = true;
prime[++primeNr] = 2;
for(int i=3; i<=nmax; i+=2) if(!c[i]) prime[++primeNr] = i;
}
ll nr(ll x) {
ll sum = 0;
for(ll i=1; i<(1<<fctNr); i++) {
ll temp = i;
int w = -1;
ll prod = 1;
int ind = 1;
while(temp) {
if(temp&1) w = -w, prod *= fct[ind];
temp = temp >> 1;
ind++;
}
sum = sum + w * (x / prod);
}
return x - sum;
}
int main() {
ifstream f("frac.in");
ofstream g("frac.out");
ll n,p; f >> n >> p;
sieve();
int k = 1;
while(prime[k]*prime[k]<=n and k<=primeNr) {
if(n%prime[k]==0) fct[++fctNr] = prime[k];
while(n%prime[k]==0) n /= prime[k];
k++;
}
if(n!=1) fct[++fctNr] = n;
ll ans = 0;
for(int i=pmax; i>=0; i--)
if(nr(ans+(1LL<<i))<p) ans += (1LL<<i);
g << ans+1;
return 0;
}