수론 + 이산 화 - 슈퍼 파워 - UVA 11752

수론 + 이산 화 - 슈퍼 파워 - UVA 11752
제목:
만약 에 하나의 수가 두 개의 서로 다른 정수 의 멱 으로 바 뀔 수 있다 면 이 수 는 하나의 수가 두 개의 서로 다른 정수 의 멱 으로 바 뀔 수 있다 면 이 수 는 하나의 수가 두 개의 서로 다른 정수 의 멱 으로 바 뀔 수 있다 면 이 수 를 The Super Power Numbers 라 고 부른다.
예 를 들 어 64 = 82 = 43 예 를 들 면 64 = 8 ^ 2 = 4 ^ 3 예 를 들 면 64 = 82 = 43
출력 [1, 2 64 − 1] 이내 의 모든 S u p e r  P o w e r   N u m b e r s 출력 [1, 2 ^ {64} - 1] 이내 의 모든 Super \ Power \ \ Numbers 출력 [1, 264 − 1] 이내 의 모든 Super Power Numbers
Sample Input
Sample Output

1
16
64
81
256
512
.
.
.

분석:
정수 X = P k 를 가정 하고 X 가 S u p e 라면  P o w e r   N u m b e r s, X = P 1 k 1 k 가 있어 야 합 니 다. 정수 X = P ^ {k} 을 가정 하면 X 가 슈퍼 \ Power \ Numbers 라면 X = P 가 있어 야 합 니 다.1 ^ {k 1k}, 정수 X = Pk 를 가정 하고 X 가 Super 라면 Power Numbers, X = P1k 1 k 가 있어 야 합 니 다.
그 중 P = P 1 k 1, 그리고 k 1 ≥ 2 그 중 P = P1 ^ {k 1}, 그리고 k1 \ \ ge 2 중 P = P1k 1, 그리고 k1 ≥ 2
이것 은 k 가 2 보다 큰 합 수 라 는 것 을 의미한다.이것 은 k 가 2 보다 큰 합 수 라 는 것 을 의미한다.이것 은 k 가 2 보다 큰 합 수 라 는 것 을 의미한다.
그리고 k 의 상 계 는 64 이 고 하 계 는 4 이다.그리고 k 의 상 계 는 64 이 고 하 계 는 4 이다.그리고 k 의 상 계 는 64 이 고 하 계 는 4 이다.
따라서 우 리 는 폭력 적 으로 (264 − 1) 14, 지수 64 까지 셀 수 있 고 판단 하면 된다.따라서 우 리 는 폭력 적 으로 (2 ^ {64} - 1) ^ {\ frac {1} {4}} 까지 셀 수 있 습 니 다. 지수 가 64 가 되면 판단 하면 됩 니 다.따라서 우 리 는 폭력 적 으로 (264 − 1) 41, 지수 64 까지 셀 수 있 고 판단 하면 된다.
조건 에 맞 는 모든 수 를 저장 하고 정렬 한 다음 에 무 게 를 판정 하고 마지막 에 출력 합 니 다.조건 에 맞 는 모든 수 를 저장 하고 정렬 한 다음 에 무 게 를 판정 하고 마지막 에 출력 합 니 다.조건 에 맞 는 모든 수 를 저장 하고 정렬 한 다음 에 무 게 를 판정 하고 마지막 에 출력 합 니 다.
주의:
경계 위 치 는 매 거 지수 가 있 을 때 u l 이 터 질 수 있 으 므 로 각별히 주의해 야 한다.경계 위 치 는 매 거 지수 가 터 질 수 있 으 니 각별히 주의해 야 한다.경계 위 치 는 매 거 지수 가 터 질 수 있 으 니 각별히 주의해 야 한다.
해결 방안 은 x i > i n f 에서 종료 합 니 다. 넘 침 을 방지 하기 위해 서 는 이전 순환 에서 x i > i n f / x 에서 미리 종료 할 수 있 습 니 다.해결 방안 은 x ^ i > inf 시 종료 합 니 다. 넘 침 을 방지 하기 위해 서 는 이전 순환 에서 x ^ i > inf / x 시 미리 종료 할 수 있 습 니 다.해결 방안 은 xi > inf 시 종료 합 니 다. 넘 치 는 것 을 방지 하기 위해 서 는 이전 순환 에서 xi > inf / x 시 미리 종료 할 수 있 습 니 다.
코드:

#include 
#include 
#include 
#include 
#include 

#define ull unsigned long long

using namespace std;

const int N=100010;
const ull inf=(1<<64)-1;

ull ans[N], idx;

bool check(int x)
{
     
    for(int i=2;i<=x/i;i++)
        if(x%i==0) 
            return false;
    return true;
}

void cal(ull x)
{
     
    ull tmp=1;
    for(int i=1;i<=64;i++)
    {
     
        tmp*=x;
        if(!check(i)) ans[idx++]=tmp;
        if(tmp>inf/x) break;
    }
}

int main()
{
     
    ans[idx++]=1;
    for(int i=2;i<=65536;i++) cal(i);
    sort(ans,ans+idx);
    int n=unique(ans,ans+idx)-ans;
    for(int i=0;i<n;i++) printf("%llu
",ans[i]);

    return 0;
}