Comments (12)
φ(m) がいろんな素因数で割れるとき速い,みたいな方法はあるので,複数ケースで時間計るのは要注意という話があります
https://ja.wikipedia.org/wiki/安全素数
https://en.wikipedia.org/wiki/Pohlig–Hellman_algorithm
from library-checker-problems.
0 2 4
で 1 と言いませんか
ちゃんと読んでないけど m が素数じゃないとき全然ダメな気がします
from library-checker-problems.
個人的には両方ほしいです 実装量がかなり変わる奴はICPCでは使い分けるので(最小有向全域木のO(VE) とO(E log V)とか
from library-checker-problems.
from library-checker-problems.
2 <= m -> 1 <= m
from library-checker-problems.
sqrt(10^9) logで100ケースも動くか?
from library-checker-problems.
unordered_map なら log が消えるみたいな主張 (うーん)
from library-checker-problems.
問題概要
- 問題ID: discrete_logarithm
- 問題名: Discrete Logarithm
Tケース与えられる。
x, y, mが与えられる。x^k = y (mod m)なるkのうち、最小を答えよ(存在しない場合-1)
入力
T
x y m
x y m
:
x y m
出力
各行に求めたもの
制約
1 <= T <= 100?(速度見ながら調整)
1 <= m <= 10^9
0 <= x, y < m
from library-checker-problems.
バグ確認!
from library-checker-problems.
0^0が未定義 1です
from library-checker-problems.
巡回に入るまでが長いケース、x = 2でmod = 2^29など
from library-checker-problems.
もっと大きい制約で解けた どうすっかな
https://loj.ac/problem/6542
http://elliptic-shiho.hatenablog.com/entry/2016/12/02/051931
from library-checker-problems.
Related Issues (20)
- [問題案] Palindromes in Deque HOT 3
- [問題案] (Addition/Multiplication/Division of Hex Big Integers) HOT 1
- [問題案] Counting Square-free numbers HOT 2
- [テストケース案] Counting Primes HOT 6
- [問題案] composition of formal power series (Large), compositional_inverse_of_formal_power_series (Large) HOT 1
- [Problem proposal] Sum of Multiplicative Function HOT 6
- License file is broken
- [Problem proposal] Vertex Add Range Contour Max on Tree HOT 2
- [テストケース案] Matching on Bipartite Graph HOT 2
- テストケース追加(convolution mod 2^64)
- [機能案] library checker の双対 HOT 2
- [問題案] Point Set Tree Path Rooted Composite Sum HOT 4
- [Problem proposal] (Range Add Range Sum) HOT 4
- テストケース Range Chmin Chmax Add Range Sum HOT 3
- [問題案] Point Set Tree Path Composite Sum HOT 2
- 問題案:2変数 FPS operations HOT 2
- [Problem proposal] counting non-decreasing path between two sequence with certain transition polynomial HOT 3
- [テストケース案] 定数項が 0 : Power Projection of Set Power Series
- Actions: All generate test failed HOT 3
- [テストケース] matrix pow / characteristic polynomial
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from library-checker-problems.