AtCoder Grand Contest 022C Remainder Games

本文主要是介绍AtCoder Grand Contest 022C Remainder Games，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：给你n个数ai,要求你将每个数mod一些数，使ai变为bi。在进行变换时，若ai与aj都要mod数p,只算一次p。求最后可得到的Σ2^pi最小值。

英文题面：

Problem Statement
Aoki is playing with a sequence of numbers a1,a2,…,aN. Every second, he performs the following operation :

Choose a positive integer k. For each element of the sequence v, Aoki may choose to replace v with its remainder when divided by k, or do nothing with v. The cost of this operation is 2k (regardless of how many elements he changes).
Aoki wants to turn the sequence into b1,b2,…,bN (the order of the elements is important). Determine if it is possible for Aoki to perform this task and if yes, find the minimum cost required.

Constraints
1≤N≤50
0≤ai,bi≤50
All values in the input are integers.
Input
Input is given from Standard Input in the following format:

N
a1 a2 … aN
b1 b2 … bN
Output
Print the minimum cost required to turn the original sequence into b1,b2,…,bN. If the task is impossible, output −1 instead.

Sample Input 1
3
19 10 14
0 3 4
Sample Output 1
160
Here’s a possible sequence of operations :

Choose k=7. Replace 19 with 5, 10 with 3 and do nothing to 14. The sequence is now 5,3,14.

Choose k=5. Replace 5 with 0, do nothing to 3 and replace 14 with 4. The sequence is now 0,3,4.

The total cost is 2^7+2^5=160.

Sample Input 2
3
19 15 14
0 0 0
Sample Output 2
2
Aoki can just choose k=1 and turn everything into 0. The cost is 21=2.

Sample Input 3
2
8 13
5 13
Sample Output 3
-1
The task is impossible because we can never turn 8 into 5 using the given operation.

Sample Input 4
4
2 0 1 8
2 0 1 8
Sample Output 4
0
Aoki doesn’t need to do anything here. The cost is 0.

Sample Input 5
1
50
13
Sample Output 5
137438953472
Aoki should mod 37

我们先观察数据范围:n，a，b都小于等于50.这意味着O(N^4)的时间复杂度都可以过这道题。

我们考虑N^4的做法，由于对于每一个数ai，都得使它mod一些数，成为bi。所以我们可以建立一个50×50的矩阵。f[i][j]表示i可以通过mod一些数变为j。

这里还有一个推论，即若可以用1~k的数完成变换，就绝不选k+1。因为2^k+1>∑2^i（i:1~k）。这是十分显然的，我们随便举个例子即可：

如2^10=1024；2^0+2^1+2^2+2^3+2^4+2^5+2^6+2^7+2^8+2^9=1+2+4+8+16+32+64+128+256+512=1023<1024。

有了这个推论，我们就可以进行枚举，从50到1枚举，如果1到i-1的数可以完成变换，就不选i。否则i必选。在我们选了i之后，就在原图中连上每个数和它mod i的边。然后我们继续从i到1进行枚举，知道我们找完为止。

那我们怎么判断两点之间是否联通呢？我们可以用floyd算法,我们进行N^3的连通性判断即可。

我们枚举n，并进行N^3的floyd，所以时间复杂度为N^4。

Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read(){char c;ll x;while(c=getchar(),c<'0'||c>'9');x=c-'0';while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
ll n,res,flag,a[55],b[55],f[55][55],d[55][55];
ll pows(ll a,ll b){ll base=1;while(b){if(b&1) base*=a;a*=a;b/=2;}return base;
}
ll check(ll x){for(ll i=0;i<=50;i++)for(ll j=0;j<=50;j++) d[i][j]=f[i][j];for(ll i=1;i<=x;i++)for(ll j=0;j<=50;j++) d[j][j%i]=1;for(ll k=0;k<=50;k++) for(ll i=0;i<=50;i++)for(ll j=0;j<=50;j++)if(d[i][k]&&d[k][j]) d[i][j]=1;for(ll i=1;i<=n;i++) if(!d[a[i]][b[i]]) return 0;return 1;
}
void go(ll x){res+=pows(2,x);for(ll i=0;i<=50;i++) f[i][i%x]=1;for(ll i=x;i>=1;i--){if(check(i-1)) continue;if(i!=x) go(i);break;}
}
int main()
{n=read();for(ll i=1;i<=n;i++) a[i]=read();for(ll i=1;i<=n;i++) b[i]=read();for(ll i=0;i<=50;i++)for(ll j=0;j<=i;j++) if(i==j) f[i][j]=1;else f[i][j]=0;for(ll i=51;i>=1;i--){if(check(i-1)) continue;if(i==51) flag=1;else go(i);break;}if(!flag) printf("%lld",res);else puts("-1");return 0;
}