首页 > 其他分享 >[ABC293E] Geometric Progression 题解

[ABC293E] Geometric Progression 题解

时间:2023-03-11 22:55:35浏览次数:43  
标签:begin end int 题解 sum bmatrix ABC293E Geometric mod

[ABC293E] Geometric Progression 题解

神中神数论

题目描述

给定整数 \(A, X, M\),求

\[\sum_{i= 0} ^ {X - 1}A^i\bmod M \]

  • \(1 \le A, M \le 10^9\)

  • \(1\le X\le 10^{12}\)

Solution1

最酷炫的一个,分治

可以发现

\[\sum_{i= 0} ^ {X - 1}A^i=\begin{cases} \sum_{i= 0} ^ {X - 2}A^i + A^{X-1} & ,X-1\bmod 2 \equiv 1 \\ \sum_{i = 0} ^ {\frac{X-1}2 }\times(A^{\frac{X-1}2} + 1) & ,X-1\bmod 2 \equiv 0 \end{cases} \]

显然时间复杂度为 \(O(\log X)\)

int solve(int a, int k)
{
    if(k == 1) return 1;
    if(k % 2) return (solve(a, k - 1) + qmi(a, k - 1)) % mod;
    return (solve(a, k / 2) * (qmi(a, k / 2) + 1)) % mod;
}

来自Jasper08大佬

Solution2

最好理解的方法,矩阵乘法

若令 \(f_i = \sum\limits_{i=0}^{X-1}A^i\),则有 \(f_i = Af_{i - 1} + 1\)。

显然可以用矩阵加速这个递推过程:

\[\begin{bmatrix} A & 1\\ 0 & 1 \end{bmatrix} \times \begin{bmatrix} f_{i-1}\\ 1 \end{bmatrix} = \begin{bmatrix} f_i\\ 1 \end{bmatrix} \]

所以初始状态 \(f_1 = 1\)。

则有

\[\begin{bmatrix} A & 1\\ 0 & 1 \end{bmatrix}^{X-1} \times \begin{bmatrix} f_{1}\\ 1 \end{bmatrix} = \begin{bmatrix} f_X\\ 1 \end{bmatrix} \]

时间复杂度:\(O(\log X)\)。

Solution3

最快的方法 / 最神仙的方法,同余方程

若令 \(S = \sum_{i=0}^{X-1}A^i\),则有 \(AS = \sum_{i=1}^XA_i\)

因此错位相减得到,\((A-1)S \equiv A^X-1\pmod {M(A-1)}\),把 \(A-1\) 移过去求逆元不可行,因为 \(A-1\) 与 \(M\) 不一定互质,不一定存在逆元。

可以证明 \((A-1)|(A^X-1\bmod M(A-1))\)。

时间复杂度:\(O(\log M)\)

signed main()
{
    if(A == 1)
    {
        write(X % mod);
        return 0;
    }
    mod = mod * (A - 1);
    int a = A, b = qmi(A, X);
    b = (b + mod) % mod;
    if(A - 1 == 0) 
    {
        cout << 0 << endl;
        return 0;
    }
    write(b / (A - 1));
 
    return 0;
}

来自 CTR_WU 大佬

标签:begin,end,int,题解,sum,bmatrix,ABC293E,Geometric,mod
From: https://www.cnblogs.com/MoyouSayuki/p/17207283.html

相关文章

  • UVA12107 题解
    前言题目传送门!更好的阅读体验?很久以前的一道搜索大模拟题目,另一篇题解的写法有点鬼畜,所以就来补篇题解。题面给你一个数字谜。修改最少次数(每次修改一个数位为空格或......
  • [POI2001][HAOI2007] 反素数 题解
    前置知识:一些关于约数的小常识。唯一分解定理对于所有正整数\(n\),一定有唯一分解方式\(n=p_1^{c_1}p_2^{c_2}\cdotsp_m^{c_m}\),其中\(p_1<p_2<\cdots<p_m\),......
  • P3530[POI2012 FES-Festival] 题解
    题面链接简要题意对于数列\(\{v_n\}\),有两种约束\(v_i=v_j+1\)和\(v_i\gev_j\),问\(\{v_n\}\)最多有多少个不同的项。解法考虑先建图,注意到如果约束图是DAG,那么......
  • CF1795 G.Removal Sequences - 题解
    记\(N(u)\)表示图上与点\(u\)相邻的点,\(p_u=deg_u-a_u\),其中\(deg_u\)为无向图上点\(u\)的度数。首先要删除\(p_u=0\)的点,同时\(\forallv\inN(u),p_v......
  • CF888D Almost Identity Permutations 题解
    CF链接:AlmostIdentityPermutationsLuogu链接:AlmostIdentityPermutations${\scr\color{Aquamarine}{\text{Solution}}}$前言这好像是一道能用数学秒掉的题目但......
  • 「THUPC 2023 初赛」欺诈游戏 题解
    写点无脑做法。设走私者的策略是\(p_i\)概率选\(i\),检查官的策略是\(q_i\)概率选\(i\)。因为两者策略均最优,所以走私者选任意一个数得到的期望收益相同,检查官选任......
  • CF1802D题解
    CF1802D题解传送门更好的阅读体验简化题意:有n个商店,每个商店卖a,b两种商品,价格分别为\(a_i,b_i\),你需要在每个商店买一个商品,并且不能在所有商店都买同一种商品,最......
  • Python - Crypto 导入失败问题解决记录
    python3.7Mac安装psycopg2$pipinstallpsycopg2...Error:pg_configexecutablenotfound....出现报错:Error:pg_configexecutablenotfound.解决参考:h......
  • P5752 [NOI1999] 棋盘分割题解
    本文来自我的洛谷博客。本题解力求使用清晰易懂的图片和文字,讲解最简洁的道理。请大家耐心地看完,注意要结合图片一起哦~~2022-8-24更改了格式与错别字2022-8-28更改......
  • python工具jupyternotebook页面打开空白问题解决方法
    jupyternotebook页面打开空白问题解决方法下载anaconda自带的jupyternotebook找到这个配置文件C:\Users\Administrator.jupyter\jupyter_notebook_config.py打开找......