大数运算取模题 AtCoder - abc275_b

简介: 大数运算取模题 AtCoder - abc275_b

题目链接与翻译

AtCoder - abc275_b

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

image.png

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

image.png

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

image.png

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

除法取模

image.png

目录
相关文章
|
7月前
|
存储
HJ26 字符串排序
HJ26 字符串排序
58 0
MT2045 斐波那契,但是是字符串
MT2045 斐波那契,但是是字符串
|
机器学习/深度学习
CF1304B Longest Palindrome(可逆转符号,数学分析,回文串)
CF1304B Longest Palindrome(可逆转符号,数学分析,回文串)
47 0
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
|
人工智能 Windows
CF617E XOR and Favorite Number(异或前缀和+莫队)
CF617E XOR and Favorite Number(异或前缀和+莫队)
70 0
|
测试技术