对一个算式取模时 模数不是质数该怎么办 请大家帮帮忙
在做算法题时 返回的结果通常要模一个数m 当要模的结果算式中含有除法 就要转化为逆元运算 用费马小定理和扩展欧几里算出那个除数关于m的逆元
但是当模的这个数不是质数的时候 那两个方法不好用 就要用这个算式 x/d%m = x%(d*m)/d 那可不可以说这个算式能替代那两种算法呢？
我觉得当除数d乘模数m超出long long 的范围的时候不行 那是不是只有这一种例外情况呢？
还有其实我也不是很明白为什么模数不是质数的时候不能用那两种算法 我是通过结果发现不对的 我看的这道题需要最终输出a/b* 10^(n+2)%1000（0<a,b,n<1000000000）
如果用逆元的话 就是a* 10^(n+2)*(b关于1000的逆元)%1000 按照模运算的规则 我把每部分都%1000 就变成了(a%1000)* (10^(n+2)%1000)*(b关于1000的逆元)%1000
这样的话10^(n+2)%1000等于0 整个式子就等于0 不是正确的结果 所以我是发现费马小定理和扩展欧几里算法 好像在这里不好用 不知道有没有大神能告诉我为什么？
一共有三个问题 希望大神们能救救我这个小白
投递蚂蚁集团等公司10个岗位 >
