ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#207930 | #3758. 拆分 | Allen123456hello | 100 | 54ms | 1380kb | C++11 | 934b | 2024-08-01 10:05:03 | 2024-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;
}
详细
小提示:点击横条可展开更详细的信息
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