模运算的运用

不定期更新在各编程网站题目中模运算的运用

多组同余

若存在元素x,对于一数组中任意某个元素e，满足
e += k * x (k取任意整数)
则只需数组一中所有e对x同余(对x取模结果相同)；
若存在有两个元素x y,对于数组一中任意某个元素e ，满足
e += ax+by(a b取任意整数)
又因为 ax+by = k * Gcd(a, b) (k取任意整数)
则只需数组一中所有e对Gcd(a, b)同余(对Gcd(a, b)取模结果相同);

题目来源：·计蒜客·两个数组

算法思想

  • 类推下去
    则只需 数组一中所有e对Gcd(数组二所有元素)同余
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    int Gcd(int a, int b)
    {
    	if(!b)
    		return a;
    	return Gcd(b, a%b);
    }
    int main()
    {
    	int n;
    	scanf("%d", &n);
    	while(n--)
    	{
    		int len1, len2;
    		cin >> len1 >> len2;
    		for(int i = 0; i < len1; ++i)
    			scanf("%d", &a[i]);
    		int gcd;
    		for(int i = 0; i < len2; ++i)
    		{
    			scanf("%d", &b[i]);
    			if(i == 0)
    				gcd = b[i];
    			else
    				gcd = Gcd(gcd, b[i]);
    		}
    //		cout << gcd << endl;
    		int flag = 0;
    		for(int i = 1; i < len1; ++i)
    		{
    			if(a[i-1]%gcd != a[i]%gcd)
    			{
    				flag = 1;
    				break;
    			}
    		}
    		if(flag)
    			cout << "No" <<endl;
    		else
    			cout << "Yes" <<endl;
    	}
    	return 0;
    }

同余方程（模线性方程）性质

若 ax = b(mod n)
则 (a-b)%n = 0, a%n == b%n;
a、b可运用于两个前缀和

题目来源·蓝桥·k倍区间

算法思想

  • 前缀和 + 同余
    b[i]记录a[i]前缀和，子区间则可用b[i]-b[j]表示(0 <= j < i)
    满足k倍区间及 (b[i]-b[j])%k==0
    于是很容易有以下代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void solve()
    {
    	for(int i = 0; i < n; ++i)
    	{
    		b[i+1] = b[i] + a[i];  //前缀和
    	}
    	int sum = 0;
    	for(int i = 0; i < n; ++i)
    	{
    		for(int j = i; j < n; ++j)
    		{
    			if((b[j+1] - b[i])%k == 0)
    				++sum;
    		}
    	}
    	cout << sum <<endl;
    }

显然n的平方复杂度会超时

  • 优化的思想
    k倍区间的个数即求多少组b[i]、b[j]满足
    (b[i]-b[j])%k==0
    同余性质得 b[i]%k == b[j]%k

对于样例
Output：
5 2
1 2 3 4 5
Input：
6
（一）得到前缀和b[] 1 3 6 10 15
（二）对 b[i]%k 得到0 1 1 0 0 1（加了个0，特殊处理b[i]%k==0的情况）1的个数为3，0的个数为3
结果有多少组呢？ C23 + C23 = 6。
最终优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
typedef long long ll;
int a[100005];
int b[100005];
map<int, int> mp;
int n, k;
void solve()
{
	mp[0] = 1; 
	for(int i = 0; i < n; ++i)
	{
		b[i+1] = (b[i] + a[i]) % k;
		++mp[b[i+1]];
	}
	ll sum = 0;
	for(int i = 0; i < n; ++i)
	{
		sum += (ll)mp[i] * (mp[i]-1) / 2;
	}
	cout << sum <<endl;
}
int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n ;++i)
	{
		scanf("%d", &a[i]);
	}
	solve(); 
	return 0;
}