QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#953570 | #10204. Heretical … Möbius | sckrt | WA | 32ms | 3968kb | C++20 | 2.5kb | 2025-03-27 21:19:57 | 2025-03-27 21:19:57 |
Judging History
answer
#include <bits/stdc++.h>
#define test(x) cout<<#x<<" = "<<x<<endl
#define endl '\n'
#define int long long
using namespace std;
const int MAXN = 1e6 + 100, N = 1e9;
int n, m;
string s;
int a[3] = {4, 9, 25}, res[3];
int isp[MAXN];
vector<int> pm;
void pre() {
int NN = sqrt(1e9) + 10;
for (int i = 2; i <= NN; ++i) {
if (isp[i] == 0)
pm.push_back(i);
for (auto p : pm) {
if (i * p > NN)
break;
isp[i * p] = 1;
if (i % p == 0)
break;
}
}
}
void solve() {
n = 200, m = 44100;
{
string s0;
for (int i = 1; i <= 10; ++i) {
cin >> s0;
s += s0;
}
}
auto chk2 = [&](int k) -> bool {
vector<int> vis(210, 1);
for (auto p : pm) {
int pp = p * p, t = k % pp;
t = (pp - t) % pp;
while (t < 200) {
vis[t] = 0;
if (s[t] != '0')
return 0;
t += pp;
}
}
for (int i = 0; i < 200; ++i)
if (vis[i] != s[i] - '0')
return 0;
return 1;
};
int vis[50] = {0};
for (int i = 0; i < 3; ++i)
for (int st = 0; st < a[i]; ++st) {
int ok = 1;
for (int j = st; j < n; j += a[i])
if (s[j] == '1') {
ok = 0;
break;
}
if (ok) {
if (res[i] > 0) {
cout << "-1";
return;
}
res[i] = st;
}
}
for (int st = 0; st < 49; ++st) {
int ok = 1;
for (int j = st; j < n; j += 49)
if (s[j] == '1') {
ok = 0;
break;
}
if (ok) {
vis[(49 - st) % 49] = 1;
}
}
vector<int> ast, ans;
for (int st = 1; st <= m; ++st) {
int ok = 1;
for (int i = 0; i < 3; ++i)
if ((st + res[i]) % a[i] != 0)
ok = 0;
if (vis[st % 49] == 0)
ok = 0;
if (ok)
ast.push_back(st);
}
for (int st : ast)
for (int i = st; i <= 1e9; i += m) {
if (chk2(i)) {
ans.push_back(i);
break;
}
}
if (ans.size() == 0)
cout << "-1";
else {
sort(ans.begin(), ans.end());
cout << ans[0];
}
}
signed main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
pre();
int tt = 1;
// cin >> tt;
while (tt--)
solve();
}
/*
11101110011011101010
11100100111011101110
11100110001010101110
11001110111011001110
01101110101011101000
11101110111011100110
01100010111011001110
11101100101001101110
10101110010011001110
11101110011011101010
01010101010101010101
10101010101010101010
01010101010101010101
10101010101010101010
01010101010101010101
10101010101010101010
01010101010101010101
10101010101010101010
01010101010101010101
10101010101010101010
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3968kb
input:
11101110011011101010 11100100111011101110 11100110001010101110 11001110111011001110 01101110101011101000 11101110111011100110 01100010111011001110 11101100101001101110 10101110010011001110 11101110011011101010
output:
1
result:
ok "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010
output:
-1
result:
ok "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
11011101110011011101 01011101100111010101 11011100110111010101 10011001110111011101 11001001110101011101 10011101010010011100 11011101010111010001 11011101110111001101 10010101010110011101 11001101110011011101
output:
5201314
result:
ok "5201314"
Test #4:
score: 0
Accepted
time: 32ms
memory: 3840kb
input:
00110111010001110110 01010111011100010010 01110101011101100101 01110111011000110111 01000111011001110111 01110111001101110101 01110110011000110011 01110011011101010101 01100111001101110111 00100101010101110110
output:
228211892
result:
ok "228211892"
Test #5:
score: 0
Accepted
time: 31ms
memory: 3840kb
input:
01110111001101110100 01110110010101110111 00010010011101010111 01100101011101110110 00110111010001110110 01110111011101110011 01110101011101100110 00110011011100110111 01010101011001110011 01110111001001010101
output:
228211884
result:
ok "228211884"
Test #6:
score: 0
Accepted
time: 29ms
memory: 3840kb
input:
00110011000001110110 01110111011100010011 01110101011101100001 01110111011100110111 01000111011001110111 01110100001101110101 01110110011000110111 01110011011101000101 01100111011101010111 00100111010101110110
output:
134965592
result:
ok "134965592"
Test #7:
score: 0
Accepted
time: 30ms
memory: 3968kb
input:
01110111001100110000 01110110011101110111 00010011011101010111 01100001011101110111 00110111010001110110 01110111011101000011 01110101011101100110 00110111011100110111 01000101011001110111 01010111001001110101
output:
134965584
result:
ok "134965584"
Test #8:
score: 0
Accepted
time: 29ms
memory: 3840kb
input:
01110111011100110011 00000111011001110111 01110001001101110101 01110110000101110111 01110011011101000111 01100111011101110100 00110111010101110110 01100011011101110011 01110100010101100111 01110101011100100111
output:
134965580
result:
ok "134965580"
Test #9:
score: 0
Accepted
time: 23ms
memory: 3968kb
input:
11001101010100011001 00011101110111011100 01010001010111011001 11011101110111001101 11010101100110001001 11011101110011011101 01011101100111011101 11011000110111010101 01011001110111011101 11001100110001001101
output:
4607430
result:
ok "4607430"
Test #10:
score: 0
Accepted
time: 16ms
memory: 3840kb
input:
11011100100101010101 11011001110111011001 11001100010101010101 10011101110111011100 00011100010111011001 11011100110101001101 11010101110110011001 11011101110011010100 01011101000111011101 11011100110111000101
output:
627338
result:
ok "627338"
Test #11:
score: 0
Accepted
time: 14ms
memory: 3968kb
input:
01110011010101010111 00100111011101110111 00110101010101110110 01110111011001110011 01110101011100100111 01110111011100110111 00010111011001110111 01110101001101110001 01110110010001110111 01110011011100010111
output:
18904
result:
ok "18904"
Test #12:
score: 0
Accepted
time: 23ms
memory: 3840kb
input:
00110111010001110010 01110111011101110011 00100101011101100111 01110101011100110111 00010111011001110111 01110111001001100001 01110110011101110111 00110011011101010101 01100100011101110111 00110111010001110110
output:
663884
result:
ok "663884"
Test #13:
score: 0
Accepted
time: 8ms
memory: 3968kb
input:
01101110101011101100 11000110111011100110 11101010101011001110 11101110110001001110 10101110010011101110 10101110010011101010 11100100111011101010 11100110101010101110 11001110111011001110 01101100101011101100
output:
999999801
result:
ok "999999801"
Test #14:
score: -100
Wrong Answer
time: 7ms
memory: 3968kb
input:
11011101010111011001 10001101110111001101 11010101010110011101 11011101100010011101 01011100100111011101 01011100100111010101 11001001110111010101 11001101010101011101 10011101110110011100 11011001010111011001
output:
999999802
result:
wrong answer 1st words differ - expected: '-1', found: '999999802'