Cod sursa(job #2661614)

Utilizator YusyBossFares Yusuf YusyBoss Data 22 octombrie 2020 13:17:48
Problema GFact Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <stdio.h>
#include <math.h>
#define PMAX 2000000000
#define QMAX 30000
#define NRdiv1PRIMMAX 15

using namespace std;

int put[NRdiv1PRIMMAX + 1], div1[NRdiv1PRIMMAX + 1];

int descfactprim(int n) {
  int i, nrdiv1;
  i = 2;
  nrdiv1 = 0;

  while (i * i <= n && n > 1) {
    while (n % i == 0) {
      n /= i;
      put[nrdiv1]++;
    }
    div1[nrdiv1++] = i;
    i++;
  }

  if (n > 1) {
    put[nrdiv1] = 1;
    div1[nrdiv1++] = n;
  }

  return nrdiv1;
}

bool test(long long x, int q, int nrdiv1) {
  int i, ok;
  long long cnt;

  ok = 1;
  i = 0;
  while (i < nrdiv1 && ok == 1) {
    cnt = 0;
    while (x && cnt < q * put[i]) {
      cnt += (long long) x / div1[i];
      x /= div1[i];
    }
    if (cnt < q * put[i])
      ok = 0;
    i++;
  }

  return ok;
}

long long cautbin(int nrdiv1, int q) {
  bool nr;
  long long st, dr, mij, sol;

  st = 1;
  dr = (long long) PMAX * QMAX;
  sol = -1;

  while (st <= dr) {
    mij = (st + dr) / 2;
    nr = test(mij, q, nrdiv1);
    if (nr) {
      sol = mij;
      dr = mij - 1;
    }
    else
      st = mij + 1;
  }

  return sol;
}

int main() {
  FILE *fin, *fout;
  int p, q, nrdiv1;

  fin = fopen("gfact.in", "r");
  fscanf(fin, "%d%d", &p, &q);
  fclose( fin );

  nrdiv1 = descfactprim(p);

  fout = fopen("gfact.out", "w");
  fprintf(fout, "%lld", cautbin(nrdiv1, q));
  fclose( fout );
  return 0;
}