题目链接与翻译
Problem Statement
给定6个非负整数,A, B, C, D, E, F,计算(a * b * c)-(d * e * f) 模 998244353后的结果
Constraints
0\leq A,B,C,D,E,F\leq 10^{18}0≤A,B,C,D,E,F≤1018
A\times B\times C\geq D\times E\times FA×B×C≥D×E×F
Input
6个非负整数,A,B,C,D,E,F
Output
输出 (A\times B\times C)-(D\times E\times F)(A×B×C)−(D×E×F)模 998244353998244353以后的结果
Sample 1
Since A\times B\times C=2\times 3\times 5=30A×B×C=2×3×5=30 and D\times E\times F=1\times 2\times 4=8D×E×F=1×2×4=8,
we have (A\times B\times C)-(D\times E\times F)=22(A×B×C)−(D×E×F)=22. Divide this by 998244353998244353 and print the remainder, which is 2222.
Sample 2
Since A\times B\times C=1000000000A×B×C=1000000000 and D\times E\times F=0D×E×F=0,
we have (A\times B\times C)-(D\times E\times F)=1000000000(A×B×C)−(D×E×F)=1000000000. Divide this by 998244353998244353 and print the remainder, which is 17556471755647.
Sample 3
We have (A\times B\times C)-(D\times E\times F)=0(A×B×C)−(D×E×F)=0. Divide this by 998244353998244353 and print the remainder, which is 00.
一些话
之前看了一个取模运算nt文章给我误导了,
说是(a-b)%m === (a%m) - (b%m)
这种取模公式是真扯淡,
如果不对运算结果再取模的话,最后的结果是可能大于m的
正篇
前提条件:
元素间运算后可能爆范围,题目又让取模
处理方法:
把每个元素先分别取模,然后元素间每一次运算后的结果都要取一次模
如果是减法或除法运算,结果需要再进行一次处理
对于减法,
如果是大数减小数,得到结果为负时不断+=m直到结果为正,
如果是小数减大数,得到结果为正时不断+=m直到结果为正,
这部分的m是大数比小数被m多剔除的部分
对于除法,
我还不会,想学的可以参考此篇
除法取模与逆元/费马小定理 - Angel_Kitty - 博客园 (cnblogs.com)
举例子:
减法:
假设a = m + 1, b = m - 1,正确的结果应该是
((m+1)-(m-1))%m
即2%m,
减法两边的元素取模后再运算:
(m+1)%m - (m-1)%m,
即1 - (m - 1) = -m,
就会出问题。
除法:
同样的,除法运算也是会出问题的
(m+1)/(m-1) 假设m = 2,
就是3 / 1 = 3;
元素取模:
1/1 = 1;
套路总结
时隔几个月回来看自己博客感觉真是又臭又长
总结一下套路方便之后查看
减法取模:
(A - B) % mod = ((A % mod) - (B % mod) +mod) % mod
除法取模