Editorial for Số nguyên tố!


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

#include<cstring>
#include<iostream>
using namespace std;

typedef unsigned long long Long;
const int MAX = 3e6;
bool isPrime[MAX + 1];
int p[MAX], nPrime;

void eratos() {
    memset(isPrime, -1, sizeof isPrime);
    isPrime[0] = isPrime[1] = 0;
    for(int i = 2; i * i <= MAX; ++i) if(isPrime[i])
        for(int j = i + i; j <= MAX; j += i) isPrime[j] = 0;
    for(int i = 0; i <= MAX; ++i)
        if(isPrime[i]) p[nPrime++] = i;
}

bool solutionExists(Long n, int k) {
    Long product = 1;
    for(int i = 0; i < k; ++i) product *= p[i];
    return product <= n;
}

void solve(Long n, int k) {
    if(!solutionExists(n, k)) cout << "-1\n";
    else {
        int l = 0, h = nPrime - k;
        while(l < h) {
            int m = (l + h + 1) / 2; bool ok = true;
            Long product = 1;
            for(int i = m; i < m + k; ++i)
                if(n / product >= (Long) p[i]) product *= p[i];
                else ok = false;
            if(ok) l = m; else h = m-1;
        }
        Long res = 1;
        for(int i = l; i < l + k; ++i) res *= p[i];
        cout << res << "\n";
    }
}

int main() {
    eratos();
    int tc; cin >> tc;
    Long n; int k;
    while(tc--) cin >> n >> k, solve(n, k);
    return 0;
}

Code mẫu của ladpro98

program c11pnum;
uses    math;
const   maxP=2642246;
        fi='';
var     a:array[1..maxP] of qword;
        sieve:array[1..maxP] of boolean;
        n:qword;
        d,k,t,tt:longint;
        inp:text;

procedure init;
var     i,j:longint;
begin
        for i:=2 to trunc(sqrt(maxP)) do
        begin
                if not sieve[i] then
                begin
                        j:=i*i;
                        while j<=maxP do
                        begin
                                sieve[j]:=true;
                                inc(j,i);
                        end;
                end;
        end;
        for i:=2 to maxP do
        if not sieve[i] then
        begin
                inc(d);
                a[d]:=i;
        end;
end;

function check(i:longint):boolean;
var     s,t:qword;
        j:longint;
begin
        s:=1;
        for j:=i to i+k-1 do
        begin
                t:=n div a[j];
                if s<=t then
                s:=s*a[j]
                else
                exit(false);
        end;
        exit(true);
end;

function cal(i:longint):qword;
var     s:qword;
        j:longint;
begin
        s:=1;
        for j:=i to i+k-1 do
        s:=s*a[j];
        exit(s);
end;

procedure process;
var     s:qword;
        i,l,r,m:longint;
begin
        s:=1;
        for i:=1 to k do
        s:=s*a[i];
        if s>n then
        begin
                writeln(-1);
                exit;
        end;
        l:=1;r:=d-k+1;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if check(m) then
                begin
                        s:=cal(m);
                        l:=m+1;
                end
                else    r:=m-1;
        end;

        writeln(s);
end;

begin

        assign(inp,fi);
        reset(inp);
        readln(inp,t);
        init;
        for tt:=1 to t do
        begin
                read(inp,n);
                read(inp,k);
                process;
        end;
        close(inp);
end.

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

int sieve[3000111];
int nprime;
long long primes[3000111];
unsigned long long n;
int k;

void init() {
    FOR(i,2,1800) if (!sieve[i]) {
        int j = i*i;
        while (j <= 3000000) {
            sieve[j] = 1;
            j += i;
        }
    }

    FOR(i,2,3000000) if (!sieve[i]) {
        ++nprime;
        primes[nprime] = i;
    }
}

void solve() {
    unsigned long long res = 0;

    FOR(i,1,nprime-k+1) {
        unsigned long long prod = 1LL;
        bool overflow = false;
        FOR(j,i,i+k-1) {
            if (prod > n/primes[j]) {
                overflow = true;
                break;
            }
            prod = prod * primes[j];
        }

        if (!overflow && prod <= n) {
            if (prod > res) res = prod;
        }
    }

    if (!res) cout << -1 << endl;
    else cout << res << endl;
}

int main() {
    init();
    int ntest; cin >> ntest;
    while (ntest--) {
        cin >> n >> k;
        solve();
    }
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) {
    stringstream ss;
    if (p >= 0)
        ss << fixed << setprecision(p);
    ss << a;
    T r;
    ss >> r;
    return r;
}
template<class T> T gcd(T a, T b) {
    T r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
template<class T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
template<class T> T sqr(T x) {
    return x * x;
}
template<class T> T cube(T x) {
    return x * x * x;
}
template<class T> int getbit(T s, int i) {
    return (s >> i) & 1;
}
template<class T> T onbit(T s, int i) {
    return s | (T(1) << i);
}
template<class T> T offbit(T s, int i) {
    return s & (~(T(1) << i));
}
template<class T> int cntbit(T s) {
    return s == 0 ? 0 : cntbit(s >> 1) + (s & 1);
}

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
    if (rsz <= 0) {
        ptr = 0;
        rsz = (int) fread(bf, 1, bfsz, stdin);
        if (rsz <= 0)
            return EOF;
    }
    --rsz;
    return bf[ptr++];
}
void ga(char &c) {
    c = EOF;
    while (!isalpha(c))
        c = gc();
}
int gs(char s[]) {
    int l = 0;
    char c = gc();
    while (isspace(c))
        c = gc();
    while (c != EOF && !isspace(c)) {
        s[l++] = c;
        c = gc();
    }
    s[l] = '\0';
    return l;
}
template<class T> bool gi(T &v) {
    v = 0;
    char c = gc();
    while (c != EOF && c != '-' && !isdigit(c))
        c = gc();
    if (c == EOF)
        return false;
    bool neg = c == '-';
    if (neg)
        c = gc();
    while (isdigit(c)) {
        v = v * 10 + c - '0';
        c = gc();
    }
    if (neg)
        v = -v;
    return true;
}

typedef pair<int, int> II;
const ld PI = acos(-1.0);
const ld eps = 1e-9;
const int dr[] = { 0, 0, -1, +1 , -1, -1, +1, +1};
const int dc[] = { -1, +1, 0, 0 , -1, +1, -1, +1};
const int inf = (int) 1e9 + 5;
const ll linf = (ll) 1e16 + 5;
const ll mod = (ll) 1e9 + 7;
const int maxn = 100 + 5;
#define ok puts("ok")

#define maxn 6000005

int test, k, size;
unsigned long long n, prime[maxn];

template<int MAXP> struct BitSieve {
    #define isOn(x) ( p[x >> 6] & ( 1 << ( (x & 63) >> 1) ) )
    #define turnOn(x) ( p[x >> 6] |= ( 1 << ( (x & 63) >> 1 ) ) )
    int p[(MAXP >> 6) + 1];
    BitSieve() {
        for (int i = 3; i * i <= MAXP; i += 2) {
            if (!isOn(i)) {
                int ii = i * i, i2 = i << 1;
                for (int j = ii; j <= MAXP; j += i2) turnOn(j);
            }
        }
    }
    bool operator [] (const int x) {
        return x > 1 && (x == 2 || ( (x & 1) && !isOn(x) ) );
    }
};

BitSieve<10000000> B;


void init(){
    size = 0;
    For(i, 2, 10000000 - 2) if(B[i]){
        prime[size++] = i;
    }
}

int main() {
//  freopen("in.txt", "r", stdin);

    init();
    cin >> test;
    Rep(run, test){
        cin >> n >> k;
        unsigned long long res = 1;
        Rep(i, k - 1) res *= prime[i];
        if(res * prime[k - 1] > n){
            cout << -1 << endl;
            continue;
        }

        for(int i = k - 1; i < size; i++){
            res = res * prime[i] / prime[i - k + 1];
            if(res > n / prime[i + 1]){
                cout << res * prime[i - k + 1] << endl;
                break;
            }
        }
    }

    return 0;
}

Code mẫu của skyvn97

#include<stdio.h>
#include<vector>
using namespace std;
typedef unsigned long long ull;
ull MAX;
const ull MAXV=3*10e5;
vector <ull> pl;
int t,c;
ull n;
int k;
bool pr[MAXV];
void eratosthene(void)
{     
     int i,j;
     for (i=2;i<MAXV;i=i+1)
         {
          if (!pr[i])
             {
              pl.push_back(i);
              for (j=2*i;j<MAXV;j=j+i) pr[j]=true;             
             }          
         }
}
void process(void)
{
     ull p1,p2;
     int i;
     scanf("%llu",&n);
     scanf("%d",&k);
     p1=1;
     for (i=1;i<=k;i=i+1)  
          p1=p1*pl[i-1];         
     if (p1>n)
        {
         printf("-1\n");
         return;
        }
     for (i=k+1;i<=pl.size();i=i+1)
         {
          p2=p1;
          p2=(p2/pl[i-k-1])*pl[i-1];          
          if (p2<p1)
             {
              printf("%llu\n",p1);
              return;
             }
          if (p2>n)
             {     
              printf("%llu\n",p1);
              return;
             }
          p1=p2;
         }
}
int main(void)
{
    eratosthene();
    scanf("%d",&t);
    for (c=1;c<=t;c=c+1) process();
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.