乘法逆元的定义很简单：若对于数字A,C存在X，使得A * X = 1（mod C），那么称X为 A 对 C 的乘法逆元。 那么乘法逆元的作用呢？比如：（求下面等式中的ans） F / A mod C = ans; 如果存在A * X = 1 (mod C); 那么两边乘起来就会有：F * X = ans（mod C）； 这样除法就转化为乘法了。。。 在上述公式A * X = 1 (mod C);中当A与C互质时，A关于模C的乘法逆元X有唯一解，如果不互质，则无解。如果C是是质数那么在1到（C-1）之间的任意数都与C互质。 这样在要求上述的ans只要求出乘法逆元X就可以了。 那么怎么求乘法逆元网上有好多些介绍但比较杂，由于是刚刚自学下面说的可能不太完整，欢迎过路的大神门多多的提意见。 乘法逆元的求法： 这里设inv（a）为a的乘法逆元。 根据这个题来说，因为数字的位数len已经确定了，又因为数字都是由输入的a，b组成的，那么就可以对 a 的个数进行枚举，这样枚举出的数字都是good number，如果设a的个数是 i ，那么 b 的个数就是 len-i ，那么该数各位数字的和就是sum = a * i + b * ( len - i ) 然后在判断sum是不是good number就知道有 i 个a 和 len-i 个 b 组成的good number数是不是excellent了，接下来貌似就是求简单的组合数C(len, i)%MOD，但是看看数据，10^6这可不是简单的组合数公式就能求出的，接下来就该用到前面说的知识了，利用前面说的乘法逆元的作用可得：因为 c ( len , i ) % MOD = ( len ! / ( i ! * ( len - i ) ! ) ) % MOD，类似上面的做法可以得出：c ( len , i ) % MOD = len ! * inv ( i ! * ( len-i ) ! )% MOD，接下来只要求出 inv ( i ! * ( len - i ) ! ) 即( i!*(len-i)! )的乘法逆元就可以了。 这里用欧拉函数结合快速幂的技巧来求： gcd(a, p)=1, t = Eula(p) 则a的逆元是 inv(a) = a^(t-1) Eula(p) 是p的欧拉函数。欧拉函数就是在(1, n)的区间里与p互素的数的个数。
那么如何求Eula(p)？ 1，p是素数，Eula(p) = p-1，根据定义可知。 2，p不是素数。Eula(p)=p-p/x (x是p的所有素因子， 对于相同因子只使用1次)
