kirika-comp

前提知識

フェルマーの小定理から、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 を求めよ。

kirika-comp

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) のとき)

kirika-comp

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 を表すと思うと、 これらについての掛け算が定義できます。このため、二分累乗法が使えます。

kirika-comp

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];
 

kirika-comp

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;