Question

Buna! Poate cineva sa rezolve problema 3318 de pe pbinfo (eratostene7)? Va rog mult! Mi-a trebui pana maine la 21:00 daca se poate...Dau tot ce vreti (follow, inima, coroana)​

Answer 1

Am facut cu doua variante, dar pentru amandoua se trece de limita de timp.

#include <iostream>

#include <fstream>

using namespace std;

ifstream fin("eratostene7.in");

ofstream fout("eratostene7.out");

int n, i, k, x, v[1000000], nr[1000000], j;

int main()

{

           fin >> n;

           int p[1000000];

           for (i = 1; i <= 1000000; i++) p[i] = 1;

v[1] = v[0] = 1;

       for (i = 2; i * i <= 1000000; i++)

       if (v[i] == 0) {

           p[i] = i;

           nr[i]=1;

           for (j = 2 * i; j <= 1000000; j = j + i) {

               v[j] = 1; p[j] = p[j] * i; nr[j] = nr[j] + 1;

           }

       }

           for (i = 1; i <= n; i++) {

               fin >> x >> k;

               if (x == p[x] && nr[x] == k) fout << "DA" << endl;

               else fout << "NU" << endl;

           }

   return 0;

}

A doua varianta

#include <iostream>

#include <fstream>

using namespace std;

ifstream fin("eratostene7.in");

ofstream fout("eratostene7.out");

int n, i, k, k2, x, d, ok;

int main()

{

   fin >> n;

   for (i = 1; i <= n; i++) {

       fin >> x >> k;

       k2 = 0;

       d = 2;

       ok = 0;

       while (x > 1) {

           if (x%d == 0) {x = x/d; ok ++; k2++;}

           else {ok = 0; d++;}

           if (ok > 1 || k2 > k) {ok = 0; x = 1;}

       }

       if (ok == 1 && k2 == k) fout << "DA" << endl;

       else fout << "NU" << endl;

   }

   return 0;

}