QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #57835 | #502. Yule Lads | Dual | 50 | 83ms | 44132kb | C++ | 581b | 2022-10-23 10:35:57 | 2022-10-23 10:36:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
int n,a[N];
int pri[N],vst[N],mu[N],tot;
inline void sieve(int n)
{
mu[1] = 0;
for(int i = 2;i <= n;i++)
{
if(!vst[i]) pri[++tot] = i,mu[i] = -1;
for(int j = 1;j <= tot && 1ll * i * pri[j] <= n;j++)
{
vst[i * pri[j]] = true;
if(i % pri[j] == 0) {mu[i * pri[j]] = 0;break;}
else mu[i * pri[j]] = -mu[i];
}
}
}
int main()
{
scanf("%d",&n);sieve(n);
int ans = 1;
// 都关灯
for(int i = 2;i <= n;i++)
if(mu[i] != 0) ++ans;
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 15
Accepted
Test #1:
score: 15
Accepted
time: 2ms
memory: 3624kb
input:
1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
2
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
3
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
4
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5
output:
4
result:
ok single line: '4'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
6
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
7
output:
6
result:
ok single line: '6'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
8
output:
6
result:
ok single line: '6'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3760kb
input:
9
output:
6
result:
ok single line: '6'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
10
output:
7
result:
ok single line: '7'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
11
output:
8
result:
ok single line: '8'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
12
output:
8
result:
ok single line: '8'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
13
output:
9
result:
ok single line: '9'
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #14:
score: 10
Accepted
time: 2ms
memory: 3732kb
input:
991
output:
603
result:
ok single line: '603'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
952
output:
579
result:
ok single line: '579'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
491
output:
301
result:
ok single line: '301'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
998
output:
608
result:
ok single line: '608'
Subtask #3:
score: 12
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #18:
score: 12
Accepted
time: 3ms
memory: 4340kb
input:
100000
output:
60794
result:
ok single line: '60794'
Test #19:
score: 0
Accepted
time: 2ms
memory: 4500kb
input:
99977
output:
60782
result:
ok single line: '60782'
Test #20:
score: 0
Accepted
time: 4ms
memory: 4552kb
input:
99782
output:
60664
result:
ok single line: '60664'
Test #21:
score: 0
Accepted
time: 3ms
memory: 4452kb
input:
99998
output:
60794
result:
ok single line: '60794'
Subtask #4:
score: 13
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #22:
score: 13
Accepted
time: 52ms
memory: 44072kb
input:
4999996
output:
3039630
result:
ok single line: '3039630'
Test #23:
score: 0
Accepted
time: 54ms
memory: 44100kb
input:
4999906
output:
3039577
result:
ok single line: '3039577'
Test #24:
score: 0
Accepted
time: 49ms
memory: 44132kb
input:
4999593
output:
3039383
result:
ok single line: '3039383'
Test #25:
score: 0
Accepted
time: 83ms
memory: 44048kb
input:
4999999
output:
3039633
result:
ok single line: '3039633'
Subtask #5:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #26:
score: 0
Runtime Error
input:
99999997
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
0%