首页 > 其他分享 >LOJ#162 【模板】光速幂

LOJ#162 【模板】光速幂

时间:2022-10-09 17:47:06浏览次数:58  
标签:LOJ ll sqrt leq 162 预处理 模板 mod

题意

这可能也是一道模板题。

给出正整数 \(x\) 和 \(n\) 个正整数 \(a_i\),求 \(x^{a_i} \bmod p\)。

对于 \(100\%\) 的数据,\(1\leq n\leq 5\times 10^6,1\leq x,a_i<p,p=99824435\color{red}2\)。

题解

\(O(\sqrt n)\ - \ O(\ 1\ )\) 光速幂板子。适用于固定底数、较多询问的快速幂查询。支持非质数模数

具体是像 \(\text{BSGS}\) 算法那样,预处理出 \(x^1,x^2,...x^{\sqrt n}\),随后预处理出 \(x^{\sqrt n},x^{2\sqrt n},...x^n\)。

然后就赢麻了。对于每个查询的指数 \(y\) ,答案即为 \(x^{y ÷ \sqrt n}\ ·x^{y\ mod \sqrt n}\)。这俩上面都是预处理好的。

代码

ll x,n;
const ll mod=998244352;
ll s[32000],b[32000];
void solve(){
	x=R,n=R;
	ll block=sqrt(mod);
	ll bas=1;
	b[0]=s[0]=bas;
	for(ll i=1;i<=block;i++){
		bas=bas*x%mod;
		s[i]=bas;
	}
	x=bas,bas=1;
	for(ll i=1;i<=block;i++){
		bas=bas*x%mod;
		b[i]=bas;
	}
	while(n--){
		ll a=R;
		wk(b[a/block]*s[a%block]%mod);
	}
	return ;
}

标签:LOJ,ll,sqrt,leq,162,预处理,模板,mod
From: https://www.cnblogs.com/rnfmabj/p/loj162.html

相关文章

  • [LOJ3138] [COI2019] LJEPOTICA
    非常简单数位dp。先差分转成前缀询问,然后记录状态\(dp_{p,num,hv,pre}\)表示当前考虑到第\(p\)位,还剩\(num\)次改变定义的机会,\(hv\)表示这一位是否考虑大小限......
  • 差分约束模板补坑与学习
    很久以前就学了差分约束,但是一直没搞懂,也懒得搞懂。今天看板子,脑补了几秒钟突然就懂了。对于一个不等式,\(x_i-x_j\lek\),可以变形:\(x_i\lex_j+k\)。这跟最短......
  • P3388 【模板】割点(割顶)
    【模板】割点(割顶)题目背景割点题目描述给出一个\(n\)个点,\(m\)条边的无向图,求图的割点。输入格式第一行输入两个正整数\(n,m\)。下面\(m\)行每行输入两个正整......
  • 模板引擎
    1、模板引擎的步骤1.1语法通过{{}}进行变量的输出:三元、对象属性、数组、表达式等点击查看代码<!DOCTYPEhtml><htmllang="en"><head><metacharset="UT......
  • LOJ 104. 普通平衡树
    1#include<bits/stdc++.h>2usingnamespacestd;3constintN=1e5+10;4intn,opt,x,val[N],fa[N],sze[N],sum[N],lc[N],rc[N],T,rt;5......
  • 力扣1627——带阈值的图连通性
    1627.带阈值的图连通性难度困难有 n 座城市,编号从 1 到 n 。编号为 x 和 y 的两座城市直接连通的前提是: x 和 y 的公因数中,至少有一个 严格大于 ......
  • idea -- mybaties -- 模板下载
    1,ctroller-->如下@GetMapping(value="/createTlzExcel")publicStringcreateTlzExcel(HttpServletResponseresponse)throwsException{Map<String,Object>exc......
  • vue-2 模板语法
    router/index.js//1、引入基础依赖importVuefrom'vue'importRouterfrom'vue-router'//2、引入要路由的页面importSmartyfrom"../components/smarty"//3、......
  • Luogu P3389【模板】高斯消元法
    题意给定一个线性方程组,对其求解。$1\leqn\leq100,\left|a_i\right|\leq{10}^4,\left|b\right|\leq{10}^4$题解因为之前贺题解的时候没有理解高斯-约......
  • 29 自定义模板功能
    在相应的app文件夹中,创建templatetags文件夹,必须是templatetags文件夹命名:注意:templatetags文件夹中必须要有__init__.py文件jd.py:fromdjangoimporttemplateregist......