UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#207930#3758. 拆分Allen123456hello10054ms1380kbC++11934b2024-08-01 10:05:032024-08-01 12:08:14

answer

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long LL;
/*
懂哥猜想:
规定一个正整数是P数这个正整数当且仅当(是质数或者小于2)
任何大于0的偶数可以写成两个P数之和
*/
vector<LL> prime;int pos;
bitset<100000005> isnotP;
bool isPbaoli(LL n){
    for (LL i=2;i*i<=n;++i){if (!(n%i)){return 0;}}return 1;
}
void euler(LL n){
    pos=0;
    prime.push_back(1145141919810LL);
    for (LL i=1;i<=n;++i){
        if (isPbaoli(n-i)&&(!isnotP[i])){
            printf("%lld %lld",i,n-i);exit(0);
        }
        if ((!isnotP[i])&&(i>=2)){
            prime.push_back(i);++pos;
        }
        for (LL j=1;j<=pos&&i*prime[j]<=n;++j){
            isnotP[i*prime[j]]=1;
            if (!(i%prime[j])){
                break;
            }
        }
    }
}
int main(){
    LL n;
    scanf("%lld",&n);
    euler(n);
    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

92

output:

3 89

result:

ok ok, f(a)+f(b)=4

Test #2:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

88

output:

5 83

result:

ok ok, f(a)+f(b)=4

Test #3:

score: 10
Accepted
time: 0ms
memory: 1228kb

input:

74

output:

1 73

result:

ok ok, f(a)+f(b)=3

Test #4:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

99496

output:

149 99347

result:

ok ok, f(a)+f(b)=4

Test #5:

score: 10
Accepted
time: 0ms
memory: 1248kb

input:

97768

output:

191 97577

result:

ok ok, f(a)+f(b)=4

Test #6:

score: 10
Accepted
time: 0ms
memory: 1248kb

input:

70744

output:

137 70607

result:

ok ok, f(a)+f(b)=4

Test #7:

score: 10
Accepted
time: 6ms
memory: 1380kb

input:

101260118

output:

1039 101259079

result:

ok ok, f(a)+f(b)=4

Test #8:

score: 10
Accepted
time: 14ms
memory: 1360kb

input:

900200416

output:

977 900199439

result:

ok ok, f(a)+f(b)=4

Test #9:

score: 10
Accepted
time: 15ms
memory: 1340kb

input:

980144336

output:

883 980143453

result:

ok ok, f(a)+f(b)=4

Test #10:

score: 10
Accepted
time: 19ms
memory: 1380kb

input:

990429172

output:

1061 990428111

result:

ok ok, f(a)+f(b)=4

Extra Test:

score: 0
Extra Test Passed