1.6.线性打表求逆元原创

这节课讲用线性达标求力元，之前讲过用飞马小定律和扩散经理的算法求乘法率元，这两种算法都是求单个的乘法率，时间复杂度是o logo p.而且我1到N的利润。时间复杂度就是on乘以那个T。而线性达标P量球力润，也就是1到N之间的一个范围之类的力源，时间复杂度可以优化成on。这意思就是。遍历一次，1到N。那么请你元都能求出来。注意X。和1同于没得PP必须是数数，如果，如果P不是数数的话，那么这个方法是。

嗯，求不出来了。我们看这个地堆的公式。N1的负一次方等于负的T÷1A，然后再乘以P余除以A的负一次方。如果P预出如果。如果PP能整除以A，那么P与除A就等于0了。那么那么这整个的求乘方里面就无法求出来，所以要求P，要求P次数数。嗯，输入输入就是1到负一次的话，那那么肯定是一的。然后AA的负一次方等于这一坨。这个P吹。它肯定是小于A的，所以第二次调用这个公式的时候，这个A它变小了。

然后再再来一次P锤，然后A他。又会变小。然后这当P与垂等于1的时候，那就直接移到B次方，自然就等于1了。这这这个时候A肯定。都都能求出来了。就是如何证明这个地推公司就是通过这个等式。T等于。PP÷A再乘以再加个P余除A，也就是被除数等于3乘以除数。然后加上语速。这个等式两边同时没得P，也就是取，然后P自然就变成0了。

然后P除盐盐，然后再加上余数，不得P。嗯，等式两边乘以A的负一次方。然后把这个A给销掉了，然后变成P除。然后右边，那自然就需要乘以A到负次方。注意语数A是产业的非常，这个地方是不不能写下去下来的，因为批语数它是一个整体。然后等式两边除以P÷A，它自然。这个T÷A相加取乘，还需要乘以那个？P余数A的负一次方。然后加上A的负一次方。然后。然后把A的负一次方移移到统一式的左边。

然后去去个。去一个符号。然后变成了负的P-A。负的P÷A向下去3，再乘以P的P余除A的负一次方。从而，这个地推公式被证明出来了。然后我们看一下各员的代码。我们看一下批量的批量球力员。首先是分配一个空间，就是。1到N-1的空间自然是N这个，这里分配了N+1的空间，意思就是有1。第第0个空间区号为0的数，嗯，数字是并没有用到，所以。

AN1=1，然后从2~2到N之间便利。然后。第一次便利自自然就是NS2。把2的负一次方给求出来。然后2的负一次方，嗯，PP÷2，那自然就等于1了。然后1到负一次方就是等于1了。就是AN1等1，然后记下一次的便利就是AN3。3这个就是P于数以3了。P余除以3，它既有可能等于1。也也可能等于2。然后。就是1到负一次方，而2到负一次方都已经求出来了，从而可以求出3到负一次方，然后一次变利。

然后就最终就把。1到N之间的利润全部给求出来了。这个上面这个是9单个的利润。单个利润跟这个多个的利润是。思是一样的。然后我们看一下运行结果。我们可以看到。预定的结果都是一样的。注注意这这这个，如果想想把那个时间复杂度优化成，嗯，必须用那个。

批量的。九力元，如果如果你你又用上了单个的九力元，那时间复杂都又变成那个N乘那个P了。