数论-同余与逆元

曾经终败给现在 2022-11-25 14:30 190阅读 0赞

### 文章目录 ###

*  同余
 *   *  一元线性同余方程
 *  逆元
 *   *  逆元与除法取模
 *  例题
 *   *  HDU-5976

# 同余 #

--------------------

两个整数 a a a和 b b b及模 m m m，如果 a a a% m = b m=b m=b% m m m，称 a a a和 b b b对 m m m同余。同余也可以理解为 a − b a-b a−b是 m m m的倍数： m ∣ ( a − b ) m|(a-b) m∣(a−b)，例如 6 ∣ ( 23 − 11 ) 6|(23-11) 6∣(23−11)，23和11对模6同余。  
同余符号计为 a ≡ b ( m o d a≡b(mod a≡b(mod  m ) m) m)。

## 一元线性同余方程 ##

a x ≡ b ( m o d ax≡b(mod ax≡b(mod  m ) m) m)，求解x的值。可以理解为 a x − b ax-b ax−b是 m m m的倍数，设倍数为 y y y，则 a x − m y = b ax-my=b ax−my=b，那么就可以用[扩展欧几里得][Link 1]求解 x x x，可是当 g c d ( a , m ) ≠ b gcd(a,m)\\neq b gcd(a,m)=b时不能用扩展欧几里得求解，这时需要结合下面的逆元。

# 逆元 #

--------------------

给出 a a a和 m m m，求解 a x ≡ 1 ( m o d ax≡1(mod ax≡1(mod  m ) m) m)，即 a x ax ax除 m m m的余数是 1 1 1。那么该方程的一个解 x x x称为 a a a模 m m m的逆元，注意这样的 x x x有很多，都称为逆。  
[扩展欧几里得可参考上一篇][Link 1]  
扩展欧几里得求逆元：

ll inv(ll a, ll m){ 
    	ll x, y;
    	ll gcd = extend_gcd(a, m, x, y);
    	return	(x % m + m) % m;//注意负数
    }

递推求逆元：

inv[1] = 1;
    for (i = 2; i < n; i++)
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;

## 逆元与除法取模 ##

逆元一重要作用就是求除法的模，首先我们看一下模运算：

*  加： ( a + b ) (a+b) (a\+b)% m = ( a m=(a m=(a% m + b m+b m\+b% m ) m) m)% m m m
 *  减： ( a − b ) (a-b) (a−b)% m = ( a m=(a m=(a% m − b m-b m−b% m ) m) m)% m m m
 *  乘： ( a ∗ b ) (a\*b) (a∗b)% m = ( a m=(a m=(a% m ∗ b m\*b m∗b% m ) m) m)% m m m
 *  除： ( a / b ) (a/b) (a/b)% m ≠ ( a m\\neq(a m=(a% m m m  / / /  b b b% m ) m) m)% m m m

显然，对于加减乘法都是正确的，但是除法不能满足，比如(100/50)%20=2，而(100%20)/(50%20)=0。这时可以用逆元求解。  
设 b b b的逆元是 k k k，则：  
 a b \\frac\{a\}\{b\} ba% m = ( a b m=(\\frac\{a\}\{b\} m=(ba% m ) ( b k m)(bk m)(bk% m ) = ( a b b k ) m)=(\\frac\{a\}\{b\}bk) m)=(babk)% m = a k m=ak m=ak% m m m  
也就是 ( a / b ) (a/b) (a/b)% m = ( a k ) m=(ak) m=(ak)% m m m

# 例题 #

--------------------

## HDU-5976 ##

[HDU-5976 Detachment][]

> **Problem Description**  
> In a highly developed alien society, the habitats are almost infinite dimensional space.  
> In the history of this planet,there is an old puzzle.  
> You have a line segment with x units’ length representing one dimension.The line segment can be split into a number of small line segments: a1,a2, … (x= a1+a2+…) assigned to different dimensions. And then, the multidimensional space has been established. Now there are two requirements for this space:  
> 1．Two different small line segments cannot be equal ( ai≠aj when i≠j).  
> 2．Make this multidimensional space size s as large as possible (s= a1∗a2\*…).Note that it allows to keep one dimension.That’s to say, the number of ai can be only one.  
> Now can you solve this question and find the maximum size of the space?(For the final number is too large,your answer will be modulo 10^9+7)  
> **Input**  
> The first line is an integer T,meaning the number of test cases.  
> Then T lines follow. Each line contains one integer x.  
> 1≤T≤10^6, 1≤x≤10^9  
> **Output**  
> Maximum s you can get modulo 10^9+7. Note that we wants to be greatest product before modulo 10^9+7.  
> **Sample Input**  
> 1  
> 4  
> **Sample Output**  
> 4

将一个数拆成若干数，求其乘积最大。  
先上结论：一个数n拆成m个数使其乘积最大，则拆成m个n/m；如果nm不整除则拆成一段连续自然数(从2开始，剩下的往前摊)；如果不限制m，则拆成最多的3，剩下的拆成2。[证明参考][Link 2]  
这题要求数不能相同，所以拆成从2开始的连续数，然后就是预处理+逆元取模即可，详见代码。

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 5e4 + 10;
    const int mod = 1e9 + 7;
    ll sum[maxn];
    void init(){ 
    	sum[0] = sum[1] = 1;
    	for (int i = 2; i < maxn; i++)
    		sum[i] = i * sum[i - 1] % mod;
    }
    ll extend_gcd(ll a, ll b, ll& x, ll& y){ 
    	if (b == 0){ 
    		x = 1; y = 0;
    		return a;
    	}
    	ll gcd = extend_gcd(b, a % b, y, x);
    	y -= x * (a / b);
    	return gcd;
    }
    ll inv(ll a, ll m){ 
    	ll x, y;
    	ll gcd = extend_gcd(a, m, x, y);
    	return	x = (x % mod + mod) % mod;
    }
    int main(){ 
    	ll t, s;
    	init();
    	scanf("%lld", &t);
    	while (t--){ 
    		scanf("%lld", &s);
    		if (s <= 4) { 
    			printf("%d\n", s);
    			continue;
    		}
    		ll n = (ll)((-1 + sqrt(8 * s + 9.0)) / 2 + 0.5);
    		while ((2 + n) * (n - 1) / 2 > s) n--;
    		int tmp = s - (2 + n) * (n - 1) / 2;//差值，
    		ll mi = 2 + tmp / (n - 1);//相乘中的最小值
    		ll mx = tmp % (n - 1) ? n + tmp / (n - 1) + 1 : n + tmp / (n - 1);//相乘中的最大值
    		ll temp = 2 + tmp / (n - 1) + n - 1 - tmp % (n - 1);//相乘中间断的那个数
    		ll ans = inv(sum[mi - 1], mod) * sum[mx] % mod;
    		if (temp <= mx)
    			ans = (ans * inv(temp, mod)) % mod;
    		printf("%lld\n", ans);	
    	}
    	return 0;
    }

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://blog.csdn.net/qq\_45034708][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得关注点赞收藏❤*

[Link 1]: https://blog.csdn.net/qq_45034708/article/details/107774390#_16
[HDU-5976 Detachment]: https://vjudge.net/problem/HDU-5976
[Link 2]: https://blog.csdn.net/islittlehappy/article/details/81148776
[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708