Gym - 102056C(2018EC final) -Heretical Möbius ——CRT，这神奇的数学公式，你改写对了吗？
- 内容介绍
- 文章标签
- 相关推荐
本文共计676个文字，预计阅读时间需要3分钟。
题目：判断一个200位的01序列是否在前1e9个沃斯乌斯值中。
给出：分析+意义因为4的倍数一定是0，9的倍数一定是0，等等，16的倍数一定是0。所以，我们可以判断一个200位的01序列是否在前1e9个沃斯乌斯值中。
题意
给出一个长为200的01序列，判断是否在前1e9个莫比乌斯*值中。（这里的莫比乌斯值加了绝对值）
分析
意到因为4的倍数一定是0，9的倍数一定是0……169的倍数一定是0。那么我们可以对4,9,25,49,121,169这6个200以内这质数平方进行考虑。
我们可以枚举起点位置 $x$ 对这6个数的模数，然后用CRT求出 $x$。对每个起点位置，暴力对比即可。不可能存在所有的mu值，只能单个求。
由于0的个数介于65~95，所以符合条件的起点位置并不多，因此不会超时。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll up = 1e9;
const int N = 5e4 + 5;
int prime[N];
bool notprime[N];
void getprime()
{
for (int i = 2; i < N; i++) {
if(!notprime[i]) prime[++prime[0]] = i;
for (int j = 1; j <= prime[0] && i * prime[j] < N; j++)
{
notprime[i * prime[j]] = 1;
if(i%prime[j]==0) break;
}
}
}
int mu(int x) { //求单个mu值
for (int i = 1; i <= prime[0] && prime[i] * prime[i] <= x; i++) {
if(x%(prime[i]*prime[i]) == 0) return 0;
if(x%prime[i] == 0) x/=prime[i];
}
return 1;
}
ll exgcd(ll a,ll b,ll &x, ll &y) {
ll g = a;
if(b==0) x=1,y=0; else g=exgcd(b,a%b,y,x),y-=x*(a/b);
return g;
}
ll inv(ll a,ll m) {
ll x, y;
ll d = exgcd(a, m, x, y);
return (d == 1) ? (x % m + m) % m : -1;
}
int ti[6], m[6] = {4, 9, 25, 49, 121, 169}, a[6];
int M;
void CRT() {
M = 1;
for(int i = 0; i < 6; i ++) M = M*m[i];
for(int i = 0; i < 6; i++) {
int Mi = M/m[i];
ti[i] = 1LL*inv(Mi, m[i])*Mi%M;
}
}
string s,t;
int check(int v, int r) {
while(v < 200) {
if(s[v] == ‘1‘) return 0;
v += r;
}
return 1;
}
int ok(int x) {
for (int i = 0; i < 200; i++)
if(mu(i+x) != s[i]-‘0‘) return 0;
return 1;
}
int ans = inf;
void dfs(int x) {
if(x == 6) {
int v = 0;
for(int i = 0; i < 6; i++) v = (v + 1LL*ti[i]*a[i]%M)%M; //v为CRT的值
if(v == 0) v = M;
while(v+199 <= up && v < ans) {
if(ok(v)) ans = v;
v = v + M;
}
return;
}
for(int i = 0; i < m[x]; i++) { //枚举余数a[i]
if(check(i, m[x])) {
a[x] = ( m[x] - i );
dfs(x+1);
}
}
}
int main(){
getprime();
CRT();
for(int i = 0; i < 10; i++) {cin >> t, s = s + t;}
int num = 0;
for(int i = 0; i < s.size(); i++)
if(s[i] == ‘0‘) num++;
if(num < 65 || num > 95) //0的个数在一个范围内
cout << -1 << endl;
else {
dfs(0);
if(ans == inf)
cout << -1 << endl;
else
cout << ans << endl;
}
return 0;
}
参考链接：
1.blog.csdn.net/BUAA_Alchemist/article/details/86652706
2.blog.csdn.net/a1214034447/article/details/86373308
3.ac.nowcoder.com/acm/contest/view-submission?submissionId=40622831
本文共计676个文字，预计阅读时间需要3分钟。
题目：判断一个200位的01序列是否在前1e9个沃斯乌斯值中。
给出：分析+意义因为4的倍数一定是0，9的倍数一定是0，等等，16的倍数一定是0。所以，我们可以判断一个200位的01序列是否在前1e9个沃斯乌斯值中。
题意
给出一个长为200的01序列，判断是否在前1e9个莫比乌斯*值中。（这里的莫比乌斯值加了绝对值）
分析
意到因为4的倍数一定是0，9的倍数一定是0……169的倍数一定是0。那么我们可以对4,9,25,49,121,169这6个200以内这质数平方进行考虑。
我们可以枚举起点位置 $x$ 对这6个数的模数，然后用CRT求出 $x$。对每个起点位置，暴力对比即可。不可能存在所有的mu值，只能单个求。
由于0的个数介于65~95，所以符合条件的起点位置并不多，因此不会超时。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll up = 1e9;
const int N = 5e4 + 5;
int prime[N];
bool notprime[N];
void getprime()
{
for (int i = 2; i < N; i++) {
if(!notprime[i]) prime[++prime[0]] = i;
for (int j = 1; j <= prime[0] && i * prime[j] < N; j++)
{
notprime[i * prime[j]] = 1;
if(i%prime[j]==0) break;
}
}
}
int mu(int x) { //求单个mu值
for (int i = 1; i <= prime[0] && prime[i] * prime[i] <= x; i++) {
if(x%(prime[i]*prime[i]) == 0) return 0;
if(x%prime[i] == 0) x/=prime[i];
}
return 1;
}
ll exgcd(ll a,ll b,ll &x, ll &y) {
ll g = a;
if(b==0) x=1,y=0; else g=exgcd(b,a%b,y,x),y-=x*(a/b);
return g;
}
ll inv(ll a,ll m) {
ll x, y;
ll d = exgcd(a, m, x, y);
return (d == 1) ? (x % m + m) % m : -1;
}
int ti[6], m[6] = {4, 9, 25, 49, 121, 169}, a[6];
int M;
void CRT() {
M = 1;
for(int i = 0; i < 6; i ++) M = M*m[i];
for(int i = 0; i < 6; i++) {
int Mi = M/m[i];
ti[i] = 1LL*inv(Mi, m[i])*Mi%M;
}
}
string s,t;
int check(int v, int r) {
while(v < 200) {
if(s[v] == ‘1‘) return 0;
v += r;
}
return 1;
}
int ok(int x) {
for (int i = 0; i < 200; i++)
if(mu(i+x) != s[i]-‘0‘) return 0;
return 1;
}
int ans = inf;
void dfs(int x) {
if(x == 6) {
int v = 0;
for(int i = 0; i < 6; i++) v = (v + 1LL*ti[i]*a[i]%M)%M; //v为CRT的值
if(v == 0) v = M;
while(v+199 <= up && v < ans) {
if(ok(v)) ans = v;
v = v + M;
}
return;
}
for(int i = 0; i < m[x]; i++) { //枚举余数a[i]
if(check(i, m[x])) {
a[x] = ( m[x] - i );
dfs(x+1);
}
}
}
int main(){
getprime();
CRT();
for(int i = 0; i < 10; i++) {cin >> t, s = s + t;}
int num = 0;
for(int i = 0; i < s.size(); i++)
if(s[i] == ‘0‘) num++;
if(num < 65 || num > 95) //0的个数在一个范围内
cout << -1 << endl;
else {
dfs(0);
if(ans == inf)
cout << -1 << endl;
else
cout << ans << endl;
}
return 0;
}
参考链接：
1.blog.csdn.net/BUAA_Alchemist/article/details/86652706
2.blog.csdn.net/a1214034447/article/details/86373308
3.ac.nowcoder.com/acm/contest/view-submission?submissionId=40622831