大数运算取模题 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

目录
相关文章
|
监控 安全 网络协议
【网络工程师必备神器】锐捷设备命令大全:一文在手,天下我有!
【8月更文挑战第22天】锐捷网络专攻网络解决方案,其设备广泛应用在教育、政府及企业等领域。本文汇总了锐捷设备常用命令及其应用场景:包括登录与退出设备、查看系统状态、接口与VLAN配置、路由与QoS设定、安全配置及日志监控等。通过示例如telnet/ssh登录、display命令查看信息、配置IP地址与VLAN、设置静态路由与OSPF、限速与队列调度、端口安全与ACL、SNMP监控与重启设备等,助力工程师高效管理与维护网络。
1549 4
|
数据可视化 Python
基因组之全局互作热图可视化
基因组之全局互作热图可视化
基因组之全局互作热图可视化
|
测试技术 Android开发 数据安全/隐私保护
脚本 | 手机大麦网脚本使用说明
这篇文章主要针对上篇文章的代码做一个使用说明
3972 0
|
存储 安全 算法
物联网中的数据加密技术
【6月更文挑战第1天】物联网中的数据加密技术
1955 21
|
算法 图形学
【推荐100个unity插件之4】OpenFracture插件实现unity3d物体破裂和切割
【推荐100个unity插件之4】OpenFracture插件实现unity3d物体破裂和切割
507 0
|
Python
【开源】PyQT+Pyserial开发的串口调试工具
【开源】PyQT+Pyserial开发的串口调试工具串口调试工具是我们做嵌入式开发常用的工具,市面上已经有很多串口调试工具了,博主写这款串口调试工具一方面是为了学习Python PyQT Pyserial 相关的知识,另一方面是也是可以为后续基于此设计更多的串口自动化工具。所以本文会详细介绍如何使用PyQT+Pyserial实现一款串口调试工具。
1173 1
【开源】PyQT+Pyserial开发的串口调试工具
|
XML 存储 开发工具
Android Studio如何将APK下载
【5月更文挑战第16天】
729 0
|
Shell PHP 数据安全/隐私保护
CTFShow-WEB入门篇命令执行详细Wp(29-40)
CTFShow-WEB入门篇命令执行详细Wp(29-40)
851 0
|
弹性计算
弹性计算Clouder认证:ECS快速入门—课时1:场景引入
弹性计算Clouder认证:ECS快速入门—课时1:场景引入
|
SQL BI OLAP
【面试必问】窗口函数全解-HIVE
【面试必问】窗口函数全解-HIVE

热门文章

最新文章