Skip to content

Instantly share code, notes, and snippets.

kirika_comp kirika-comp

Block or report user

Report or block kirika-comp

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
View Zi-ring-theory.txt
Z[i] 上の整数論
Z[i] はかなり性質がよい。
(i) Z[i] は ユークリッド整域である。これは単項イデアル整域であることと、一意分解整域であることを含意する。
(ii) Q(i) の整数環 (整数たちのなす環) である。つまり、 Q(i) の整数基底の一つは {1, i} である。こうならない例は例えば Q(\sqrt{5}) である。 (整数基底は{1, (1+\sqrt{5})/2})
Z の上の素元 p (有理素数と呼ぶ) を Z[i] の上でみたときの挙動は、以下の3パターンに類別できる。
1. ある Z[i] の素元 P に対して、 (p) = (P)^2 となるパターン (p = 2 のみ。このとき (P) = (1 + i)) (p は 体拡大 Q(i)/Q で分岐するという)
2. ある Z[i] の素元 P に対して、 (p) = (P) となるパターン (p = 3 (mod 4) のとき)
2. ある Z[i] の異なる素元 P, Q に対して、 (p) = (P)(Q) となるパターン (p = 1 (mod 4) のとき)
View mod_sqrtについて.md

前提知識

フェルマーの小定理から、a^(p-1)=1 (mod p)であることに注意しましょう。 a = x^2 (mod p) となる x が存在する場合、aを平方剰余、そうで無い場合aを平方非剰余と呼びます。 pが奇素数の時、0を除くと平方剰余と平方非剰余の割合は1:1です。 また、a!=0 (mod p) のときa^((p-1)/2) は mod p で 1 か -1 かのどちらかですが、aが平方剰余のとき1、平方非剰余のとき-1です。

問題

ある x について a = x^2 (mod p) が成り立つ a が与えられる。この時、x を求めよ。

View BROCLK.md

Broken Clock u=cos(a)が与えられるから、cos(ta)を求めよ、という問題です。

(部分点についてのあれこれ)

満点解法について説明します。ここで天下り的ですが、cos(a)とsin(a)=sqrt(1-u^2)を考えて、(cos(ta),sin(ta))をcos(a),sin(a)の式で表すことを考えます。

de Moivreの定理から、cos(ta)+i sin(ta) = (u + sqrt(1-u^2)i)^t です。ここで、ペア(x, y) が複素数x + sqrt(1-u^2)yi を表すと思うと、 これらについての掛け算が定義できます。このため、二分累乗法が使えます。

View generic-dijkstra.cpp
using namespace std;
typedef long long int lint;
typedef pair<int, lint> pil;
typedef pair<lint, int> pli;
typedef pair<lint, lint> pll;
const int N = 100100;
int n;
vector<pil> edges[N];
View garner.java
class Lib{
/* Verify
http://codeforces.com/contest/903/submission/33247715
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2647639
*/
/* 参考 http://math314.hateblo.jp/entry/2015/05/07/014908 */
static long extgcd(long a,long b,long[]x) {
for (long u = x[1] = 1, v = x[0] = 0; a!=0;){
long q = b / a;
long r=x[0]-q*u;
You can’t perform that action at this time.