QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#953361 | #10204. Heretical … Möbius | sckrt# | TL | 74ms | 3712kb | C++20 | 3.7kb | 2025-03-27 19:03:49 | 2025-03-27 19:03:50 |
Judging History
answer
#include <bits/stdc++.h>
#define test(x) cout<<#x<<" = "<<x<<endl
#define endl '\n'
#define ll long long
#define lll __int128
#define int long long
using namespace std;
const int MAXN = 1e5 + 100, N = 1e9;
int n, m;
string s;
int a[3] = {4, 9, 25}, res[3];
vector<int> tmp;
ll max_factor;
inline ll fpow(ll x,ll y,ll mod)
{
ll ans=1;
while(y)
{
if(y&1) ans=((lll)ans*x)%mod;
x=((lll)x*x)%mod;y>>=1;
}
return ans;
}
inline ll gcd(ll a,ll b)
{
return b ? gcd(b,a%b) : a;
}
inline bool miller_rabin(ll x)
{
if(x==2) return 1;
if(x==46856248255981l||x==1||(x&1)==0) return 0;
ll u=x-1,ct=0;
while((u&1)==0) u/=2,ct++;
for(int i=1;i<11;i++)
{
ll a=rand()%(x-1)+1;
ll xt=fpow(a,u,x);
if(xt==1) continue;
for(int j=1;j<=ct;j++)
{
ll y=(lll)xt*xt%x;
if(y==1&&xt!=1&&xt!=x-1) return 0;
xt=y;
}
if(xt!=1) return 0;
}
return 1;
}
inline ll pollard(ll x)
{
ll s=0,t=0,c=rand()%(x-1)+1,val=1;
int stp=0,goal=1;
for(goal=1;;goal<<=1,s=t,val=1)
{
for(stp=1;stp<=goal;++stp)
{
t=((lll)t*t+c)%x;
val=(lll)val*abs(t-s)%x;
if(stp%127==0)
{
ll d=gcd(val,x);
if(d>1) return d;
}
}
ll d=gcd(val,x);
if(d>1) return d;
}
}
void fac(ll x)
{
if(x==1) return;
ll p=x;
if(miller_rabin(x))
{
tmp.push_back(x);
return;
}
while(p>=x) p=pollard(x);
int cnt=0;
while(x%p==0) x/=p,++cnt;
fac(x);fac(p);
}
bool chk(int k) {
tmp.clear();
fac(k);
for(auto x:tmp)
if(k%(x*x)==0) return 0;
return 1;
}
// bool chk(int k) {
// for (int i = 2; i * i <= k; ++i) {
// int cnt = 0;
// while (k % i == 0)
// k /= i, ++cnt;
// if (cnt > 1)
// return 0;
// }
// return 1;
// }
void solve() {
n = 200, m = 44100;
{
string s0;
for (int i = 1; i <= 10; ++i) {
cin >> s0;
s += s0;
}
}
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) {
int ok = 1;
for (int t = 0; t < n; ++t) {
if (chk(t + i) != s[t] - '0')
ok = 0;
}
if (ok) {
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);
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
11101110011011101010 11100100111011101110 11100110001010101110 11001110111011001110 01101110101011101000 11101110111011100110 01100010111011001110 11101100101001101110 10101110010011001110 11101110011011101010
output:
1
result:
ok "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010
output:
-1
result:
ok "-1"
Test #3:
score: 0
Accepted
time: 74ms
memory: 3712kb
input:
11011101110011011101 01011101100111010101 11011100110111010101 10011001110111011101 11001001110101011101 10011101010010011100 11011101010111010001 11011101110111001101 10010101010110011101 11001101110011011101
output:
5201314
result:
ok "5201314"
Test #4:
score: -100
Time Limit Exceeded
input:
00110111010001110110 01010111011100010010 01110101011101100101 01110111011000110111 01000111011001110111 01110111001101110101 01110110011000110011 01110011011101010101 01100111001101110111 00100101010101110110