글 읽기 - 맞왜틀

gs25 2년 전 0

제 풀이의 개요는 다음과 같습니다. 먼저 루트N 이상인 소수 k 개의 제곱을 각각 v에 넣어줍니다. 그리고 v의 최대원소를 Max_prime_power로 정의해줍니다.

이제 세재곱 이상부터는 소수의 N제곱이 Max_prime_power 보다 작을때까지 넣어줍니다. 2의 64제곱보다 작아야되니깐 61 제곱까지 반복해줍니다. 그후 v를 정렬하고 k번째 원소를 출력합니다. 모두 N 이상을 기준으로 했기에 문제는 초과이므로 N=N+1 까지 해줍니다.

제풀이에서 틀린 부분을 모르겠는데 계속 틀렸습니다가 뜹니다. 제곱부분에서 소수들이 크므로 그부분은 밀러 라빈 판정법을 적용시켰고 나머지는 일반적인 루트까지 판별하는 소수 판정법을 이용했습니다. (제 컴퓨터에서 1**18, 100000 넣어도 빠르게 돌아갑니다) 어디서 틀렸는지 도저히 모르겠습니다.ㅜㅜ 도움 부탁드립니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef tuple<int, int, int> ti3;
typedef tuple<int, int, int, int> ti4;
typedef stack<int> si;
typedef queue<int> qi;
typedef priority_queue<int> pqi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef tuple<ll, ll, ll> tl3;
typedef tuple<ll, ll, ll, ll> tl4;
typedef stack<ll> sl;
typedef queue<ll> ql;
typedef priority_queue<ll> pql;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>ordered_set;

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };
const int ddx[8] = { 0,0,1,1,1,-1,-1,-1 }, ddy[8] = { 1,-1,1,0,-1,1,0,-1 };
ll POW(ll a, ll b, ll MMM) { ll ret = 1; for (; b; b >>= 1, a = (a * a) % MMM)if (b & 1)ret = (ret * a) % MMM; return ret; }
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a / GCD(a, b) * b; }
ll INV(ll a, ll m) {
	ll m0 = m, y = 0, x = 1;
	if (m == 1)	return 0;
	while (a > 1) {
		ll q = a / m;
		ll t = m;
		m = a % m, a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0) x += m0;
	return x;
}
pll EXGCD(ll a, ll b) {
	if (b == 0) return { 1,0 };
	auto t = EXGCD(b, a % b);
	return { t.second,t.first - t.second * (a / b) };
}
bool OOB(ll x, ll y, ll N, ll M) { return 0 > x || x >= N || 0 > y || y >= M; }
#define X first
#define Y second
#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(a) ((int)(a.size()))
#define sf1(a) cin >> a
#define sf2(a,b) cin >> a >> b
#define sf3(a,b,c) cin >> a >> b >> c
#define sf4(a,b,c,d) cin >> a >> b >> c >> d
#define sf5(a,b,c,d,e) cin >> a >> b >> c >> d >> e
#define sf6(a,b,c,d,e,f) cin >> a >> b >> c >> d >> e >> f
#define pf1(a) cout << (a) << ' '
#define pf2(a,b) cout << (a) << ' ' << (b) << ' '
#define pf3(a,b,c) cout << (a) << ' ' << (b) << ' '<< (c) << ' '
#define pf4(a,b,c,d) cout << (a) << ' ' << (b) << ' '<< (c) << ' '<< (d) << ' '
#define pf5(a,b,c,d,e) cout << (a) << ' ' << (b) << ' '<< (c) << ' '<< (d) << ' '<< (e) << ' '
#define pf6(a,b,c,d,e,f) cout << (a) << ' ' << (b) << ' '<< (c) << ' '<< (d) << ' '<< (e) << ' ' << (f) << ' '
#define pf0l() cout << '\n';
#define pf1l(a) cout << (a) << '\n'
#define pf2l(a,b) cout << (a) << ' ' << (b) << '\n'
#define pf3l(a,b,c) cout << (a) << ' ' << (b) << ' '<< (c) << '\n'
#define pf4l(a,b,c,d) cout << (a) << ' ' << (b) << ' '<< (c) << ' '<< (d) << '\n'
#define pf5l(a,b,c,d,e) cout << (a) << ' ' << (b) << ' '<< (c) << ' '<< (d) << ' '<< (e) << '\n'
#define pf6l(a,b,c,d,e,f) cout << (a) << ' ' << (b) << ' '<< (c) << ' '<< (d) << ' '<< (e) << ' ' << (f) << '\n'
#define pfvec(V) for(auto const &t : V) pf1(t)
#define pfvecl(V) for(auto const &t : V) pf1(t); pf0l()

ull mul(ull x, ull y, ull m) {
	return (ull)((__int128)x * y % m);
}
ull lpow(ull x, ull y, ull m) {
	ull r = 1;
	x %= m;
	while (y) {
		if (y & 1) r = mul(r, x, m);
		x = mul(x, x, m);
		y >>= 1;
	}
	return r;
}
bool MR(ull n, ull a) {
	if (n % a == 0) return 0;
	int cnt = -1;
	ull d = n - 1;
	while (!(d & 1)) {
		d >>= 1;
		cnt++;
	}
	ull p = lpow(a, d, n);
	if (p == 1 or p == n - 1) return 1;
	while (cnt--) {
		p = mul(p, p, n);
		if (p == n - 1) return 1;
	}
	return 0;
}
// deterministic in 1-2**78
bool isPrime_MR(ll n) {                                         //// 밀러 라빈을 이용한 소수 판정함수
	for (auto p : { 2,3,5,7,11,13,17,19,23,29,31,37 }) {
		if (n == p) return 1;
		if (n > 40 && !MR(n, p)) return 0;
	}
	if (n <= 40) return 0;
	return 1;
}


long long N;
int k;
long long Max_prime_power;
vector <long long> v{};

bool isPrime(long long n) {                                    ///// 일반적인 소수 판정함수
	long long i = 2;
	if (n == 2) return true;
	else if (n % 2 == 0) return false;
	for(i=3;i*i<=n;i=i+2){
		if (n % i == 0) return false;
	}
	return true;
}



long long POW(long long n, int k) {long long re = 1; int t = k; while (t > 0) { re *= n; t = t - 1; } return re;}

long long n_bigger_k_power(long long N, int k) {               // N 이상인 k 거듭제곱수 최소 
	
	if (N == 1) return 1;
	if (k >= N - 1) return 2;
	

	double t = pow(N, 1 / k);

	long long a = 1;
	long long b = 1000000010;
	long long mid;
	while (b >= a) {
		if (b == a + 1) {
			if (POW(a, k) < N && POW(b, k) >= N) return b;
		}
		mid = (a + b) / 2;
		if (POW(mid, k) == N) return mid;
		else if (POW(mid, k) > N) b = mid;
		else { a = mid; }
	}
}

void f(long long N, int exp){            /// N 이상인 소수의 exp 거듭제곱 들을 v에 넣어준다.
	if (exp == 2) {
		long long s = n_bigger_k_power(N, exp);
		long long test = s;
		int cnt = 0;
		while (cnt != k) {
			if (isPrime_MR(test)) { v.push_back(test*test); cnt += 1; }
			test += 1;
		}
		Max_prime_power = v.back();
		return;
	}

	else {
		long long s = n_bigger_k_power(N, exp);
		long long test = s;
		while (POW(test, exp) <= Max_prime_power) {
			if (isPrime(test)) v.push_back(POW(test, exp));
			test += 1;
		}



	}
	

}

int main(void) {
	// cout << isPrime(31622795) << "\n";
	cin >> N >> k;
	N = N + 1;
	f(N, 2);
	f(N, 3);
	f(N, 5);
	f(N, 7);
	f(N, 11);
	f(N, 13);
	f(N, 17);
	f(N, 19);
	f(N, 23);
	int i = 23;
	for (i = 25; i < 64; i++) {
		if (isPrime(i)) f(N, i);
	}

	sort(v.begin(), v.end());
	cout << v[k - 1];
}

nick832 9달 전 0

이분은 이미 해결하신 듯 하지만 혹시 비슷한 사람이 있을까 댓글 남깁니다.

Pow(a, b)가 1e19를 넘어가면서 long long overflow가 나면 결과가 이상해질 수 있음에 유의하세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

맞왜틀

gs25 2년 전 0

nick832 9달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말