牛客Wannafly挑战赛13-BJxc军训-费马小定理、分式取模、快速幂
2024-09-01 01:14:19
参考:https://blog.csdn.net/qq_40513946/article/details/79839320
传送门:https://www.nowcoder.com/acm/contest/80/B
题意:输入n,m,求 (n*n-m)/n*n 在 取模998244353下的解;
思路:
题目给出的条件是费马小定理,那么可以知道 x负一次方等于x的(p-2)次mod(MOD) ,所以只要快速幂求出x的(p-2) 就可以了,时间复杂度 O(logMod)。
ac代码:
#include <iostream>
using namespace std; typedef long long ll;
const int md = ;
ll fpow(ll a,ll n)//快速幂
{
ll res = ;
while(n)
{
if(n&)
res = res*a%md;
a = a*a%md;
n>>=;
}
return res;
}
int main(){
int n,m;
cin>>n>>m;
ll t = n*n-m;
ll ans = t%md*(fpow( n*n , md-)%md)%md;
cout<<ans<<endl; return ;
}
最新文章
- Struts 2开发基本流程
- 关于Oracle10G在库内导数据时,用到的更新语句----ZT
- MFC的BeginWaitCursor和EndWaitCursor函数
- Apache+php在windows下的安装和配置
- iOS开发--即时通讯
- poj 1659 Frogs&#39; Neighborhood Havel-Hakimi定理 可简单图定理
- 类库dll引用不成功问题
- JS 事件对象和事件冒泡
- chroot 的用途
- 1630/2023: [Usaco2005 Nov]Ant Counting 数蚂蚁
- 《精通python网络爬虫》笔记
- V4L2学习记录【转】
- 《算法》BEYOND 部分程序 part 1
- Linux内核分析作业 NO.4
- .net自定义控件Control、WebControl、CompositeControl
- MYSQL数据库设计之字段选择原则
- vue路由-基础
- IntelliJ IDEA使用hibernate
- EF上下文容器,保存线程唯一性
- HDU1074(状态压缩DP)