Heretical … Möbius

C++(g++ 7.5.0) 解法, 执行用时: 304ms, 内存消耗: 708K, 提交时间: 2022-11-02 18:58:35

#include <bits/stdc++.h>

#define ll long long

const int N = 6 , MAX_NUM = 1e9 , MAX_N = N + 5 , MAX_M = 31622 + 5 ;

std::vector<int> pri , val , st[MAX_N] ;
std::vector<int> upri = {2 , 3 , 5 , 7 , 11 , 13} , upri2 = {4 , 9 , 25 , 49 , 121 , 169} ;

char s[MAX_M] ;
bool ap[MAX_M] , tg[MAX_M] ;
int n , pM , M , Mi[MAX_N] , Mi_inv[MAX_N] ;

int qpow(int a , int t , int M) {
	int s = 1 ; a %= M ;
	for (; t ; a = (ll)a * a % M , t >>= 1)
		if (t & 1) s = (ll)s * a % M ;
	return s ;
}

void init() {
	int N = 31623 ;
	for (int i = 2 ; i <= N ; ++i)
		if (!ap[i]) {
			pri.push_back(i) ;
			for (int j = i + i ; j <= N ; j += i) ap[j] = 1 ;
		}
}

void dfs(int x , int num) {
	if (x == N) {
		val.push_back(num) ;
		if (num + M + n - 1 <= MAX_NUM) val.push_back(num + M) ;
	}
	for (auto &y : st[x]) dfs(x + 1 , (num + (ll)y * Mi[x] % M * Mi_inv[x] % M) % M) ;
}

bool check(int x) {
	for (int i = 0 ; i < n ; ++i) tg[i] = 0 ;
	for (auto &p : pri) {
		int v = p * p , L = (x + v - 1) / v * v ;
		for (; L - x < n ; L += v) tg[L - x] = 1 ;
	}
	for (int i = 0 ; i < n ; ++i) {
		char c = tg[i] ? '0' : '1' ;
		if (c != s[i]) return 0 ;
	}

	return 1 ;
}

int main() {
	init() ;
	M = pM = 1 ;
	for (int i = 0 ; i < N ; ++i) M *= upri2[i] , pM *= upri[i] ;
	for (int i = 0 ; i < N ; ++i) Mi_inv[i] = qpow((Mi[i] = M / upri2[i]) , upri2[i] / upri[i] * (upri[i] - 1) - 1 , upri2[i]) ;

	///

	n = 200 ;
	for (int i = 0 ; i < n ; ++i) {
		char c = getchar() ;
		for (; c != '0' && c != '1' ; c = getchar()) ;
		s[i] = c ;
	}

	///

	for (int i = 0 ; i < N ; ++i)
		for (int j = 0 ; j < upri2[i] ; ++j) {
			int v = upri2[i] ; bool ok = 1 ;
			for (int k = j ; k < n ; k += v) ok &= (s[k] == '0') ;
			if (ok) st[i].push_back((v - j) % v) ;
		}

	int siz = st[0].size() ;
	for (int i = 1 ; i < N ; ++i) siz *= st[i].size() ;

	if (!siz || siz > pM) {printf("-1\n") ; return 0 ;}
	dfs(0 , 0) ;

	std::sort(val.begin() , val.end()) ;
	for (auto &x : val)
		if (check(x)) {
			printf("%d\n" , x) ;
			return 0 ;
		}
	printf("-1\n") ;

	return 0 ;
}

C++ 解法, 执行用时: 145ms, 内存消耗: 648K, 提交时间: 2022-05-19 17:11:13

#include<bits/stdc++.h>
using namespace std;
const int a[]={4,9,25,49,121,169};
int pri[500500],M=1,t[10];
int x,y,val[220],q[50505],head;
bool vis[200200],mark[220];
char str[220];
vector<int> g[10];
inline void init() {
	int top=0,N=1e5;
	for(int i=2;i<N;++i) {
		if(!vis[i]) pri[top++]=i;
		for(int j=0;(j<top)&&(pri[j]*i<N);++j) {
			vis[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}
inline bool check(int p,int v) {
	for(int i=p;i<200;i+=v) {
		if(str[i]=='1') return 0;
	} 
	return 1;
}
inline void euclid(int a,int b)
{
    if(!b) {
        x=1;
        y=0;
    } else {
        euclid(b,a%b);
        int tem=x;
        x=y;
        y=tem-a/b*y;
    }
}
inline bool judge(int c)
{
	for(int i=0;i<200;++i) {
		val[i]=c+i;
		mark[i]=1;
	}
	int eng=c+200,v=sqrt(eng);
	for(int i=0;pri[i]<=v;++i) {
		int p=c/pri[i]*pri[i];
		if(p<c) p+=pri[i];
		while(p<eng) {
			if(val[p-c]%(pri[i]*pri[i])==0) {
				mark[p-c]=0;
			}
			val[p-c]/=pri[i];
			p+=pri[i];
		}
	}
	for(int i=0;i<200;i++) {
		if(mark[i]!=str[i]-'0') return 0;
	}
	return 1;
}
inline void dfs(int p,int ret)
{
	if(p==6) {
		q[head++]=ret;
		if(ret+M<=1e9-199) q[head++]=ret+M;
		return ;
	}
	for(int i=0;i<g[p].size();++i) {
		int v=g[p][i];
		dfs(p+1,(ret+1ll*M/a[p]*t[p]*v)%M);
	}
}
int main() {
	init();
	for(int i=0;i<10;++i) {
		scanf("%s",str+i*20);
	}
	int ret = 1;
	for(int i=0;i<6;++i) { 
		for(int j=0;j<a[i];++j) {
			if(check(j,a[i])) g[i].push_back((a[i]-j)%a[i]);
		}
		ret*=g[i].size();
	}
	if(ret>10000) return 0*puts("-1"); 
	for(int i=0;i<6;++i) {
		M*=a[i];
	}
	for(int i=0;i<6;++i) {
		int Mi=M/a[i];
		euclid(Mi,a[i]);
		t[i]=(x+a[i])%a[i];
	}
	dfs(0,0);
	int ans=-1;
	sort(q,q+head);
	head=unique(q,q+head) - q;
	for(int i=0;i<head;++i) {
		if(judge(q[i])) {
			ans=q[i];
			break;
		}
	}
	printf("%d\n",ans);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 901ms, 内存消耗: 512K, 提交时间: 2019-11-01 16:31:58

#include <bits/stdc++.h>

using namespace std;

const int N = 200;
const int MAX = 1e9;
const int SQ = sqrt(MAX);

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  string pattern;
  for (int i = 0; i < 10; ++i) {
    string s;
    cin >> s;
    pattern += s;
  }
  int ans = MAX - N + 2;
  vector<bool> isprime(SQ + 1, true);
  vector<int> primes;
  for (int i = 2; i <= SQ; ++i) {
    if (isprime[i]) {
      primes.push_back(i);
      for (int j = i + i; j <= SQ; j += i) {
        isprime[j] = false;
      }
    }
  }
  bool ed = false;
  auto solve = [&](int l) {
    if (clock() > CLOCKS_PER_SEC * 0.9) {
      ed = true;
      return;
    }
    int r = l + N - 1;
    string s(N, '1');
    for (auto p : primes) {
      if (p * p > r) {
        break;
      }
      int q = p * p;
      for (int i = (l + q - 1) / q * q; i <= r; i += q) {
        s[i - l] = '0';
        if (pattern[i - l] == '1') {
          return;
        }
      }
    }
    if (s == pattern) {
      ans = l;
      ed = true;
    }
  };
  for (int i = 1; i <= 44100; ++i) {
    bool ok = true;
    for (int j = 0; j < N; ++j) {
      if (((i + j) % 4 == 0 || (i + j) % 9 == 0 || (i + j) % 25 == 0 || (i + j) % 49 == 0) && pattern[j] == '1') {
        ok = false;
        break;
      }
    }
    if (ok) {
      for (int j = i; j < ans; j += 44100) {
        solve(j);
        if (ed) {
          break;
        }
      }
    }
    if (ed) {
      break;
    }
  }
  if (ans == MAX - N + 2) {
    ans = -1;
  }
  cout << ans << "\n";
  return 0;
}

详情