好久不登洛谷了, 最近翻了一下之前的一个帖子, 当时应该有其他事 没后续跟进了
题目
https://www.luogu.com.cn/problem/P1036
n个数
选k个出来和是质数的方案数
范围
n<=20
ai<=5e6
1s
128MB
题解
数筛TLE
https://www.luogu.com.cn/record/25067342
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);
bool p[100000010];
int ans = 0;
int a[30];
int n,k;
void dfs(int idx,int picked,int cnt){
if(picked == k){
ans+=!p[cnt];
return ;
}
if(n - idx < k-picked)return ;
dfs(idx+1,picked+1,cnt+a[idx]);
dfs(idx+1,picked,cnt);
}
int main(){
cin>>n>>k;
rep(i,0,n){
scanf("%d",a+i);
}
p[1] = 1;
rep(i,2,10001){
if(p[i] == 1)continue;
for(int j=i*i;j<100000001;j+=i){
p[j] = 1;
}
}
dfs(0,0,0);
cout<<ans<<endl;
return 0;
}
|
循环到根号n判质数竟然过了?而且搜到的一堆题解都是这样做
https://www.luogu.com.cn/record/25067748
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);
int ans = 0;
int a[30];
int n,k;
bool pp(int v){
if(v==1)return 1;
int maxv = int(sqrt(v))+2;
rep(i,2,maxv){
if(v%i==0 && v!=i){
return 1;
}
}
return 0;
}
void dfs(int idx,int picked,int cnt){
if(picked == k){
ans+=!pp(cnt);
return ;
}
if(n - idx < k-picked)return ;
dfs(idx+1,picked+1,cnt+a[idx]);
dfs(idx+1,picked,cnt);
}
int main(){
cin>>n>>k;
rep(i,0,n){
scanf("%d",a+i);
}
dfs(0,0,0);
cout<<ans<<endl;
return 0;
}
|
问题
虽然当时发了帖子, 但是里面都在喷我表达不规范 XD, 没人给我说是数据其实很小的问题
https://www.luogu.com.cn/discuss/153208
数筛 是$O(sum + 2^n)$
而上面AC的代码是$O(max(2^n, sqrt(sum) \cdot 2^k))$
如果真如题目所说的数据范围, 其实数筛更有可能过大数据, 然而实际数筛TLE了
也有老哥说n实测出来最大是7,(7的话那的确第二种没啥问题), 那题目说你妈n<=20呢?
https://www.luogu.com.cn/discuss/347995
造数据
通过简单的尝试,生成了以下数列
1
2
| for i in range(20):
print(5000000-1-6*i)
|
1
2
| 20 11
4999999 4999993 4999987 4999981 4999975 4999969 4999963 4999957 4999951 4999945 4999939 4999933 4999927 4999921 4999915 4999909 4999903 4999897 4999891 4999885
|
这数据下
数筛0.88s
后面方法1.022s
电脑配置i7-7700HQ
编译命令clang++ -o Main Main.cpp -std=gnu++17 -O2 -g -Wall -Wcomma -Wextra -fsanitize=integer,undefined,null,alignment
真题解 Miller robin + 特殊判定序列, 这个可以极快判定64位以内的质数
https://www.luogu.com.cn/record/73708925
关于质数判别之前做PE时也写过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef uint64_t ull;
#define pb push_back
#define rep(i,a,n) for (ll i=a;i<n;i++)
ll quick_p(ll b, ll p,const ll mod){
ll r = 1;
while(p){
if(p%2)(r*=b)%=mod;
(b*=b)%=mod;
p/=2;
}
return r%mod;
}
ll mr(ll base,ll v){
if(base > v)return true;
ll startp = v-1;
while(startp%2 == 0)startp>>=1;
ll p = startp;
ll r = quick_p(base,p,v);
while(p != v-1){
if(r == v-1)return true;
if(r == 1)return p == startp;
p*=2;
(r*=r)%=v;
}
return false;
}
bool is_prime_64(ll v){
if(v < 2)return false;
if(v < 4)return true;
if((v % 6) % 4 != 1)return false;
ll test_g[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
rep(i,0,7){
if(!(mr(test_g[i],v)))return false;
}
return true;
}
int ans = 0;
int a[30];
int n,k;
void dfs(int idx,int picked,int cnt){
if(picked == k){
ans+=is_prime_64(cnt);
return ;
}
if(n - idx < k-picked)return ;
dfs(idx+1,picked+1,cnt+a[idx]);
dfs(idx+1,picked,cnt);
}
int main(){
cin>>n>>k;
rep(i,0,n){
scanf("%d",a+i);
}
dfs(0,0,0);
cout<<ans<<endl;
return 0;
}
|