We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
1 parent 0978216 commit f9fa259Copy full SHA for f9fa259
Design/1622.Fancy-Sequence/Readme.md
@@ -14,7 +14,7 @@
14
15
所以我们发现了一个规律，如果当前的化简算子是{mul,add}的时候，我们想要append一个新的数字nums[i]时，我们不直接append原始的数值，我们append一个虚拟的数值val用来“抵消”这对算子的影响，即使得```nums[i] = val*mul+add```。这样我们调用getIdx(i)的时候，仍然apply当前的化简算子{mul,add}得到val*mul+add，恰好就还原了真实的nums[i]。即使此后的{mul,add}可能会更新为{mul',add'}，但是val只是抵消了i之前的运算符的效果，并不会影响i之后的运算的作用，所以当再次调用getIdx(i)的时候，就可以放心地将{mul',add'}用在val上然后输出答案。
16
17
-接下来的一个关键问题，我们试图得到这个“抵消”后的val时，发现```nums[i] = val*mul+add```并不能保证得到一个整数的```val= (nums[i]-add) / mul```。如果存储的是小数的话，此后的误差会越来越大。怎么办呢？事实上，我们并不需要存一个真实的val，我们只要存一个与val关于M同余的值就行了，我们记做val'。因为val'与val（关于M）同余，那么val'*mul+add就会与val*mul+add同余，也就是和最终的答案同余。而题目要求输出的就是将答案对M取模的结果。
+接下来的一个关键问题，我们试图得到这个“抵消”后的val时，发现```nums[i] = val*mul+add```并不能保证得到一个整数的```val= (nums[i]-add) / mul```。如果存储的是小数的话，此后的误差会越来越大。怎么办呢？事实上，我们并不需要存一个真实的val，我们只要存一个与val关于M同余的值就行了，我们记做val'。因为val'与val（关于M）同余，那么```val'*mul+add```就会与```val*mul+add```同余，也就是和最终的答案同余。而题目要求输出的就是将答案对M取模的结果。
18
19
想求```(nums[i]-add) / mul```关于M的同余，不能用“(nums[i]-add)关于M的同余”去除以“mul关于M的同余”，因为除法不满足 (a/b)%M = (a%M) / (b%M) 。正确的答案是 ```(nums[i]-add) * inv(mul)```。其中inv(mul)称之为mul的逆元。满足如下关系的a和b称之为逆元：
20
```
0 commit comments