QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#953346 | #10204. Heretical … Möbius | sckrt# | TL | 0ms | 0kb | C++20 | 3.7kb | 2025-03-27 18:53:09 | 2025-03-27 18:53:10 |
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];
int pri[MAXN],isp[MAXN],cnt;
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;
}
}
bool fac(ll x)
{
if(x==1) return 1;
ll p=x;
if(miller_rabin(x))
return 1;
while(p>=x) p=pollard(x);
int cnt=0;
while(x%p==0) x/=p,++cnt;
if(cnt>1) return 0;
return fac(x)&&fac(p);
}
bool chk(int k) {
return fac(k);
}
// 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() {
srand(time(0));
// 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
*/
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
11101110011011101010 11100100111011101110 11100110001010101110 11001110111011001110 01101110101011101000 11101110111011100110 01100010111011001110 11101100101001101110 10101110010011001110 11101110011011101010