QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179512#6512. Completely Multiplicative FunctionClHg2WA 95ms8360kbC++141.3kb2023-09-14 21:56:472023-09-14 21:56:47

Judging History

你现在查看的是最新测评结果

  • [2023-09-14 21:56:47]
  • 评测
  • 测评结果:WA
  • 用时:95ms
  • 内存:8360kb
  • [2023-09-14 21:56:47]
  • 提交

answer

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

namespace {
using std::cin;
using std::cout;
using std::int64_t;

const int kN = 1.0e6, kMaxN = kN + 5;
int n, k;
int f[kMaxN];
bool is_prime[kMaxN];
std::vector<int> primes;

void Sieve(int n) {
  std::fill_n(is_prime + 1, n, true), is_prime[1] = false;

  for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) primes.emplace_back(i);

    for (int prime : primes) {
      int j = i * prime;
      if (j > n) break;
      is_prime[j] = false;
      if (i % prime == 0) break;
    }
  }
}

void Solve() {
  cin >> n >> k;
  std::fill_n(f + 1, n, 1);
  int sum = n;

  for (int prime : primes) {
    if (prime > n) break;

    for (int i = prime; i <= n; i += prime) {
      sum -= f[i], f[i] = -f[i / prime], sum += f[i];
    }

    if (sum < k) {
      for (int i = prime; i <= n; i += prime) {
        sum -= f[i], f[i] = f[i / prime], sum += f[i];
      }
    }
  }

  if (sum != k) {
    cout << "-1\n";
  } else {
    for (int i = 1; i <= n; ++i) cout << f[i] << " ";
    cout << "\n";
  }
}
}  // namespace

int main() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  Sieve(kN);
  int t;
  cin >> t;
  while (t--) Solve();
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 6668kb

input:

4
4 2
10 0
10 1
10 10

output:

1 -1 1 1 
1 -1 -1 1 -1 1 -1 -1 1 1 
-1
1 1 1 1 1 1 1 1 1 1 

result:

ok ok (4 test cases)

Test #2:

score: 0
Accepted
time: 35ms
memory: 4756kb

input:

11475
1 0
1 1
2 0
2 1
2 2
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
5 5
6 0
6 1
6 2
6 3
6 4
6 5
6 6
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
10 0
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
11 0
11 1
11 2
11 3
11...

output:

-1
1 
1 -1 
-1
1 1 
-1
1 -1 1 
-1
1 1 1 
1 -1 -1 1 
-1
1 -1 1 1 
-1
1 1 1 1 
-1
1 -1 -1 1 1 
-1
1 -1 1 1 1 
-1
1 1 1 1 1 
1 -1 -1 1 -1 1 
-1
1 -1 -1 1 1 1 
-1
1 1 1 1 -1 1 
-1
1 1 1 1 1 1 
-1
1 -1 -1 1 -1 1 1 
-1
1 -1 -1 1 1 1 1 
-1
1 1 1 1 -1 1 1 
-1
1 1 1 1 1 1 1 
1 -1 -1 1 -1 1 1 -1 
-1
1 -1 -1 1...

result:

ok ok (11475 test cases)

Test #3:

score: 0
Accepted
time: 42ms
memory: 6084kb

input:

8825
151 0
151 1
151 2
151 3
151 4
151 5
151 6
151 7
151 8
151 9
151 10
151 11
151 12
151 13
151 14
151 15
151 16
151 17
151 18
151 19
151 20
151 21
151 22
151 23
151 24
151 25
151 26
151 27
151 28
151 29
151 30
151 31
151 32
151 33
151 34
151 35
151 36
151 37
151 38
151 39
151 40
151 41
151 42
151 ...

output:

-1
1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 1 1 1 -1 1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1...

result:

ok ok (8825 test cases)

Test #4:

score: 0
Accepted
time: 64ms
memory: 6380kb

input:

5675
201 1
201 3
201 5
201 7
201 9
201 11
201 13
201 15
201 17
201 19
201 21
201 23
201 25
201 27
201 29
201 31
201 33
201 35
201 37
201 39
201 41
201 43
201 45
201 47
201 49
201 51
201 53
201 55
201 57
201 59
201 61
201 63
201 65
201 67
201 69
201 71
201 73
201 75
201 77
201 79
201 81
201 83
201 85...

output:

1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 1 1 1 -1 1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 ...

result:

ok ok (5675 test cases)

Test #5:

score: 0
Accepted
time: 55ms
memory: 5924kb

input:

20000
100 15
90 62
96 81
98 52
93 86
91 60
96 50
96 71
96 85
97 88
94 72
100 76
98 75
93 81
100 93
98 13
96 47
96 25
100 21
94 46
100 75
90 66
91 89
100 33
98 73
92 61
96 57
97 11
97 92
98 49
90 11
100 21
99 32
99 48
96 87
90 15
99 67
99 14
94 90
94 30
94 56
93 66
98 16
99 52
90 63
95 3
97 53
100 58...

output:

-1
1 1 1 1 1 1 -1 1 1 1 1 1 1 -1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 -1 1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 -1 1 1 1 1 1 1 -1 1 1 1 1 1 1 
-1
1 1 1 1 -1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1 1 1 1 -1 1 1 1 -1 ...

result:

ok ok (20000 test cases)

Test #6:

score: 0
Accepted
time: 55ms
memory: 4824kb

input:

2000
949 642
993 9
982 214
953 437
930 248
958 429
908 294
918 155
901 704
979 943
914 603
932 75
937 638
973 793
942 933
924 146
945 221
927 415
963 818
974 483
911 538
977 900
967 875
973 473
929 575
956 657
911 864
925 221
968 271
984 427
918 165
901 222
902 207
973 573
924 672
933 398
915 742
93...

output:

-1
1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 1 1 1 -1 1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1...

result:

ok ok (2000 test cases)

Test #7:

score: 0
Accepted
time: 53ms
memory: 6180kb

input:

200
9838 512
9347 1159
9523 2665
9663 3980
9571 5990
9753 7856
9971 4152
9134 2898
9998 1207
9979 6128
9529 3228
9712 186
9039 444
9889 4916
9913 8859
9017 2702
9009 5996
9530 7408
9796 4101
9012 6258
9640 387
9898 7876
9377 9261
9411 3253
9021 6315
9782 4053
9926 1466
9099 8288
9055 6535
9025 5135
...

output:

1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 -1 1 -1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 -1 -1 1 1 -1 1 -1 1 -1 1 1 1 1 1 -1 1 1 1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 1 -1 -1 -1 1 -1 1 -1 1 -1 1 1 1 -1 -1 1 1 1 1 -1 -1 -1 1 1 1 -1 -1 1 1 -1 1 1 -1 -1 1 -1 1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 1 -1 -...

result:

ok ok (200 test cases)

Test #8:

score: 0
Accepted
time: 61ms
memory: 6244kb

input:

20
90507 59204
96310 58712
92092 14116
96425 96030
95334 94968
93822 14586
90820 46806
97408 72190
96658 69846
97170 85209
90451 52316
96323 16545
99773 79252
95584 83458
96029 34401
92457 70513
91434 56310
92414 57838
99360 21269
97083 46554

output:

-1
1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 -1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 -1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1...

result:

ok ok (20 test cases)

Test #9:

score: 0
Accepted
time: 89ms
memory: 6736kb

input:

2000
993 531
937 717
973 529
938 264
916 804
970 682
986 758
990 792
945 297
923 429
900 296
978 286
970 196
973 637
919 607
999 317
961 533
992 580
955 579
910 590
929 625
993 127
975 769
964 186
931 703
943 121
931 289
917 873
931 433
929 453
994 340
929 159
925 641
932 14
972 188
920 630
904 450
...

output:

1 1 1 1 -1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1 1 1 1 -1 -1 1 1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1 1 -1 1 1 -1 1 -1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 -1 1 -1 1 1 1 1 -1 1 -1 1 1 ...

result:

ok ok (2000 test cases)

Test #10:

score: 0
Accepted
time: 90ms
memory: 6812kb

input:

200
9968 3218
9925 1157
9357 1869
9966 7214
9751 5367
9138 3080
9692 3630
9037 945
9599 7085
9980 6224
9644 5034
9617 9389
9096 7494
9167 551
9192 6928
9554 2490
9346 6788
9739 5011
9503 3233
9194 3384
9636 8708
9236 2492
9086 442
9056 988
9659 1721
9277 6409
9760 704
9311 9067
9506 3726
9865 3917
9...

output:

1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 1 1 -1 -1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 -1 ...

result:

ok ok (200 test cases)

Test #11:

score: 0
Accepted
time: 90ms
memory: 5884kb

input:

20
96292 38540
90149 45119
94200 56900
91425 49799
97794 30448
94908 39674
91567 79135
96778 22736
94676 36484
96116 29030
97088 94818
91818 89166
99993 52141
91742 67804
92834 46148
95581 3825
92703 62665
93540 37722
92647 4751
95811 7419

output:

1 1 -1 1 1 -1 1 1 1 1 -1 -1 1 1 -1 1 1 1 1 1 -1 -1 1 -1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 1 1 1 -1 1 1 -1 1 -1 -1 -1 1 -1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 -1 1 1 -1 -1 1 1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 ...

result:

ok ok (20 test cases)

Test #12:

score: 0
Accepted
time: 91ms
memory: 8360kb

input:

2
920441 457343
920448 817692

output:

1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1...

result:

ok ok (2 test cases)

Test #13:

score: 0
Accepted
time: 95ms
memory: 5840kb

input:

20
90366 15660
90189 7689
94205 64885
96566 45098
90231 5747
99982 41670
94607 33325
99134 87902
97470 29006
97786 9086
96591 89877
91172 56240
93161 16433
98920 10612
92108 59732
97408 87050
99538 64116
93948 46898
90744 26852
96611 49165

output:

1 -1 1 1 -1 -1 1 -1 1 1 -1 1 1 -1 -1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 1 -1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 1 -1 -1 -1 1 1 1 -1 1 1 1 -1 1 -1 1 -1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 1 -1 1 1 -1 -1 1 1 1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 1 1 -1 1 1 1 -1 -1 1 1 -1 1 1 1 -1 1 -1 -...

result:

ok ok (20 test cases)

Test #14:

score: -100
Wrong Answer
time: 89ms
memory: 6948kb

input:

20
90026 58888
97807 41133
90547 17929
98248 55572
91647 813
90429 90325
93761 14287
94144 32220
95385 60333
99222 32380
93887 27285
99946 73352
99594 84098
97714 69942
95139 73915
96016 30178
96586 20808
98014 68376
90414 19068
93310 21952

output:

1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 -1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 ...

result:

wrong answer ans finds the answer, but out doesn't (test case 5)