最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

歡迎光臨散文網(wǎng) 會(huì)員登陸 & 注冊(cè)

淺談擴(kuò)展 BSGS

2023-07-28 19:52 作者:wukaichen888 0人讀過 | 我要投稿

聽 sbh 大佬講數(shù)論，講得當(dāng)然比老師好，很感動(dòng)，記筆記

給出 $a$ ， $b$ ， $p$ ，求最小非負(fù)整數(shù)解 $x$ ?滿足? $a%5Ex%5Cequiv%20b%5C%20(mod%5C%20p)$

其實(shí)是個(gè)分塊算法

先說 BSGS，當(dāng) $a$ ， $p$ 互質(zhì)時(shí)的做法

考慮對(duì)指數(shù) $x$ ?進(jìn)行分塊，顯然有解時(shí)? $0%5Cle%20x%5Clt%20p$

則令 $t%3D%5Clceil%5Csqrt%7Bp%7D%5Crceil$ ， $x$ 定然能表示為 $i%5Ctimes%20t-j$ ，其中 $1%5Cle%20i%20%5Cle%20t$ ， $1%5Cle%20j%5Cle%20t$

$a%5E%7Bi%5Ctimes%20t-j%7D%5Cequiv%20b%5C%20(mod%5C%20p)$

$a%5E%7Bi%5Ctimes%20t%7D%5Cequiv%20b%5Ctimes%20a%5Ej%5C%20(mod%5C%20p)$

預(yù)處理枚舉 $j$ ?用哈希表將 $b%5Ctimes%20a%5Ej$ ?存下

然后枚舉 $i$ ?判斷 $a%5E%7Bi%5Ctimes%20t%7D$ ?是否出現(xiàn)

復(fù)雜度? $O(%5Csqrt%7Bn%7D)$

不互質(zhì)就是 Ex_BSGS 惹

$a%5Ex%5Cequiv%20b%5C%20(mod%5C%20p)$ ， $g%3Dgcd(a%2Cp)%5Cgt1$

$a%5E%7Bx-1%7D%5Ctimes%20a%5Cequiv%20b%5C%20(mod%5C%20p)$

$a%5E%7Bx-1%7D%5Ctimes%20%5Cfrac%7Ba%7D%7Bg%7D%5Cequiv%20%5Cfrac%7Bb%7D%7Bg%7D%5C%20(mod%5C%20%5Cfrac%7Bp%7D%7Bg%7D)$

$b%3D1$ ?時(shí) $x%3D0$ ，否則如果 $g%5Cnmid%20b$ ，原方程無解

然后繼續(xù)拆前面的 $a%5E%7Bx-1%7D$ ?直到 $a$ ， $p$ ?互質(zhì)

$a%5E%7Bx-k%7D%5Ctimes%5Cfrac%7Ba%5Ek%7D%7B%5Cprod%20g_i%7D%5Cequiv%20%5Cfrac%7Bb%7D%7B%5Cprod%20g_i%7D%5C%20(mod%5C%20%5Cfrac%7Bp%7D%7B%5Cprod%20g_i%7D)$

$a%5E%7Bx-k%7D%5Cequiv%20%5Cfrac%7Bb%7D%7B%5Cprod%20g_i%7D%5Ctimes%5Cfrac%7B%5Cprod%20g_i%7D%7Ba%5Ek%7D%5C%20(mod%5C%20%5Cfrac%7Bp%7D%7B%5Cprod%20g_i%7D)$

然后直接 BSGS，還有一堆特判

一定要用擴(kuò)歐求逆元（

標(biāo)簽：

淺談擴(kuò)展 BSGS的評(píng)論 (共條)

浠水县| 建水县| 祁门县| 武宁县| 林芝县| 高密市| 旬邑县| 灵丘县| 南昌市| 大渡口区| 尚义县| 宁波市| 大冶市| 兴文县| 玉门市| 泽州县| 海口市| 湘潭市| 鄱阳县| 洛浦县| 越西县| 潢川县| 海宁市| 静海县| 房产| 彭州市| 周宁县| 马公市| 阆中市| 湖州市| 河南省| 秦安县| 衡山县| 扶绥县| 龙陵县| 岚皋县| 瑞丽市| 合作市| 龙井市| 天门市| 桂东县|