大步小步攻擊演算法_完全版
先膜拜一下AekdyCoin大神….可以看看他的空間,有詳細的講解 不錯的大步小步演算法,可以秒掉poj_2417, poj_3243這種題 struct hash { int a, b, next; } Hash[MAXN << 1]; int flg[MAXN 66]; […]
數論
1/13ページ
大步小步演算法（BSGS）及擴充套件 & bzoj 2480
大步小步演算法用於解決離散對數問題： 求滿足ax≡y(modp)a^x \equiv y \pmod p的最小自然數xx，其中aa、pp互質，或者報告無解。 根據尤拉定理，aϕ(p)≡1(modp)a^\phi(p) \equiv 1 \pmod p，所以，如果有解，必然有一個在[0,ϕ(p))[0 […]
- 2018.07.26
- BSGS演算法（大步小步演算法）, 大步小步演算法, 數論,
大步小步演算法 (BSGS演算法)
大步小步演算法是專門用來求解a^x = b(mod n)這種方程的，這種問題也稱為離散對數問題。 已知a，b，n，且n為素數，求x。 模板如下 #include <iostream> #include <cstdio> #include <map> using n […]
BSGS演算法學習小記（大步小步演算法）
簡介 先看一個式子xy≡z(modp)，z是質數x^y≡z(\mod p)，z是質數 現在只知道x和z，要求y。 大步小步演算法（BSGS，Baby Steps Giant Steps）就是解決這個問題。 演算法流程 暴搜的列舉範圍 根據費馬小定理：xp−1≡1x^{p-1}≡1。 如果y已經列舉到 […]
- 2018.07.25
- ————單個題目———, NIM, nim中文, nim演算法, nim遞迴,
Nim遊戲—改 博弈論 解題報告
Nim遊戲·改(nim.c/cpp/pas) 題目描述 眾所周知的Nim遊戲是這樣的：有n堆石子，小A和小B輪流取石子，小A先操作，每次選擇一堆石子，在這堆中取走任意多個石子，最後沒有石子可取的人輸。現在為了加強Nim遊戲難度，每堆非空石子有一次額外的特殊機會，即耗掉這個機會，然後什麼也不拿走，而其 […]
HDU 2204 Eddy’s 愛好(容斥原理、給定n求滿足p=m^k <= n的p的個數)
題目連結： HDU 2204 Eddy’s 愛好 題意； 給一個nn，在p∈[1,n]p\in [1, n]範圍滿足mk=p(m≥1,k>1m^k=p(m \geq 1, k > 1的數字pp的個數。 資料範圍：1≤n≤10181 \leq n \leq 10^{18} 分析： 一開始我 […]
各子區間和的異或和
http://acm.tju.edu.cn/toj/showp4114.html 好感動~ 終於過了 要使得(sum(r)−sum(l−1))mod2k 1≥2k 其實就是兩種情況 sum(l−1)mod2k 1≤(sum(r)mod2k 1)−2k 且 0≤sum(l−1)mod2k 1 的，也可 […]
51nod 2026 Gcd and Lcm 杜教篩 數論
題意 已知f(x)=∑d|xμ(d)∗df(x)=\sum_{d|x}\mu(d)*d 現在請求出下面式子的值 ∑i=1n∑j=1nf(gcd(i,j))∗f(lcm(i,j))\sum\limits_{i=1}^n\sum\limits_{j=1}^nf(gcd(i,j))*f(lcm(i,j)) […]
【51nod 2026】Gcd and Lcm
題目 已知 f(x)=∑d|xμ(d)∗df(x)=\sum_{d|x}μ(d)∗d 現在請求出下面式子的值 ∑ni=1∑nj=1f(gcd(i,j))∗f(lcm(i,j))\sum_{i=1}^{n}\sum_{j=1}^{n}f(gcd(i,j))∗f(lcm(i,j)) 由於值可能過大所以請 […]
[HEOI2016/TJOI2016]求和
題意 求 ∑i=0n∑j=0iSij2jj!mod998244353″ role=”presentation”>∑i=0n∑j=0iSji2jj!mod998244353∑i=0n∑j=0iSij2jj!mod998244353 […]