Cod sursa(job #3372426)

Utilizator Lapush05alexandru Lapush05 Data 3 noiembrie 2026 20:19:34
Problema Frac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define int long long
using namespace std;

int pinex(int a, int b) {//cate numere x <= a au (x, b) != 1
    int factori_primi[20], nr = 0;
    for(int i = 2; i * i <= b; i++) {
        if(b % i == 0) {
            factori_primi[nr] = i;
            nr++;
            while(b % i == 0) {
                b = b / i;
            }
        }
    }
    if(b > 1) {
        factori_primi[nr] = b;
        nr++;
    }
    int sol = 0;
    for(int i = 1; i < (1 << nr); i++) {
        int p = 1;
        int nrb = 0;
        for(int bit = 0; bit < nr; bit++) {
            if(i & (1 << bit)) {
                nrb++;
                p = p * factori_primi[bit];
            }
        }
        if(nrb % 2) {
            sol += a / p;
        } else {
            sol -= a / p;
        }
    }
    return sol;
}

int f(int a, int b) {
    return a - pinex(a, b);
}

signed main() {
    ifstream cin("frac.in");
    ofstream cout("frac.out");
   int n, p;
   cin >> n >> p;
   int st=1;
   int dr=1e15;
   int sol=0;
   while(st<=dr)
   {
       int mid=(st+dr)/2;
       if(f(mid,n)>=p)
       {
           sol=mid;
           dr=mid-1;
       }
       else
       {
           st=mid+1;
       }
   }
   cout << sol;

}