結果

問題 No.981 一般冪乗根
ユーザー keymoonkeymoon
提出日時 2020-01-28 21:19:28
言語 C#(csc)
(csc 3.9.0)
結果
RE  
実行時間 -
コード長 7,088 bytes
コンパイル時間 1,001 ms
コンパイル使用メモリ 111,616 KB
実行使用メモリ 23,168 KB
最終ジャッジ日時 2024-10-09 14:00:42
合計ジャッジ時間 43,347 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
evil_60bit1.txt RE -
evil_60bit2.txt RE -
evil_60bit3.txt RE -
evil_hack RE -
evil_hard_random RE -
evil_hard_safeprime.txt RE -
evil_hard_tonelli0 RE -
evil_hard_tonelli1 RE -
evil_hard_tonelli2 RE -
evil_hard_tonelli3 RE -
evil_sefeprime1.txt RE -
evil_sefeprime2.txt RE -
evil_sefeprime3.txt RE -
evil_tonelli1.txt RE -
evil_tonelli2.txt RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;

public static class P
{
    public static void Main()
    {
        Action abort = () => { Console.WriteLine(-1); Environment.Exit(0); };

        var line = Console.ReadLine();
        Assert(!Regex.IsMatch(line, @"^\d+ \d+  \d+$"));

        var pka = line.Split().Select(int.Parse).ToArray();
        var p = pka[0];
        var k = pka[1];
        var a = pka[2];

        Assert(2 <= k && k <= 1000);
        Assert(2 <= p && p <= 1000000007);
        Assert(1 <= a && a < p);

        ModInt.Mod = p;

        //有限体Z/pZの原始根gを一つ求め、
        var g = GetPrimitiveRoot(p);
        //そのgについてのaの指数を求める。
        var aIndex = Log(a, g);
        //これによって、Z/(p-1)Z上でのa/kを求める問題に帰着できる
        //∵x^k≡a(mod p) ⇔ (g^xInd)^k≡(g^aInd)(mod p) ⇔ (xInd)*k≡aInd(mod p-1)
        //x=a/kとすると、kx=aより、aはZ/(p-1)Z上でik(i∈ℕ)と等しい必要がある。
        //これは、Z/(p-1)Z上において指数がgcd(k, p - 1)で割り切れる要素のみで構成される群の要素と等しい。
        var step = GCD(k, p - 1);
        //よって、stepを生成元として(p-1)を法とする加法によって生成される巡回群の位数orderは、
        var order = (p - 1) / step;

        //まず、aがその巡回群に乗っていない場合、除算は不可能。
        if (aIndex % step != 0) abort();

        //Z/orderZ上でのa,kの指数はそれぞれ、
        var aIndexOnZOrderZ = aIndex / step;
        var kIndexOnZOrderZ = k / step;

        //ここで、Z/orderZ上でのa/kの指数は
        var aPerKIndex = (aIndexOnZOrderZ * GetInverse(kIndexOnZOrderZ, order)) % order;
        //Z/orderZはZ/(p-1)Zの部分群なので、Z/(p-1)Zにおいても指数は等しい。よって、
        Console.WriteLine(Power(g, aPerKIndex));
    }

    static int GetPrimitiveRoot(long m)
    {
        var subgroupOrders = new List<long>();
        var order = m - 1;
        if ((order & 1) == 0)
        {
            while ((order & 1) == 0) order >>= 1;
            subgroupOrders.Add((m - 1) / 2);
        }
        for (long i = 3; i * i <= order; i += 2)
            if (order % i == 0)
            {
                while (order % i == 0) order /= i;
                subgroupOrders.Add((m - 1) / i);
            }
        if (order != 1) subgroupOrders.Add((m - 1) / order);

        for (int g = 2; g < m; g++)
        {
            if (subgroupOrders.Any(x => Power(g, x) == 1)) continue;
            return g;
        }
        throw new Exception();
    }

    static int Log(ModInt a, ModInt g)
    {
        long mulOrder = ModInt.Mod - 1;
        ModInt x = 1;
        int step = 9;
        long xAInd = 0;
        long xGInd = 0;
        ModInt waiting = 1;
        long waitingAInd = 0;
        long waitingGInd = 0;
        while (true)
        {
            for (int i = 0; i < step; i += 3)
            {
                x *= a; xAInd++;
                if (x == waiting) goto found;
                x *= x; xAInd = (xAInd << 1) % mulOrder; xGInd = (xGInd << 1) % mulOrder;
                if (x == waiting) goto found;
                x *= g; xGInd++;
                if (x == waiting) goto found;
            }
            step <<= 1;
            waiting = x;
            waitingAInd = xAInd;
            waitingGInd = xGInd;
        }
        found:;
        var aInd = Abs(xAInd - waitingAInd);
        var gInd = Abs(xGInd - waitingGInd);
        //a^aInd==g^gInd⇔a==g^(gInd/aInd)
        var gcd = GCD(mulOrder, aInd);
        if (gInd % gcd != 0) return -1;
        var subGroupOrder = mulOrder / gcd;
        return (int)(((gInd / gcd) * GetInverse(aInd / gcd, subGroupOrder)) % subGroupOrder);
    }

    static ModInt Power(ModInt n, long m)
    {
        ModInt pow = n;
        ModInt res = 1;
        while (m > 0)
        {
            if ((m & 1) == 1) res *= pow;
            pow *= pow;
            m >>= 1;
        }
        return res;
    }

    static void Assert(bool cond)
    {
        if (!cond) throw new Exception();
    }


    static long GCD(long a, long b)
    {
        while (true)
        {
            if (b == 0) return a;
            a %= b;
            if (a == 0) return b;
            b %= a;
        }
    }

    static long GetInverse(long a, long MOD)
    {
        long div, p = MOD, x1 = 1, y1 = 0, x2 = 0, y2 = 1;
        while (true)
        {
            if (p == 1) return x2 + MOD; div = a / p; x1 -= x2 * div; y1 -= y2 * div; a %= p;
            if (a == 1) return x1 + MOD; div = p / a; x2 -= x1 * div; y2 -= y1 * div; p %= a;
        }
    }
}



struct ModInt
{
    public static int Mod
    {
        get
        {
            return MOD;
        }
        set
        {
            MOD = value;
            POSITIVIZER = (long)MOD << 31;
        }
    }
    static int MOD = 1000000007;
    static long POSITIVIZER = ((long)MOD) << 31;
    long Data;
    public ModInt(long data) { if ((Data = data % MOD) < 0) Data += MOD; }
    public static implicit operator long(ModInt modInt) => modInt.Data;
    public static implicit operator ModInt(long val) => new ModInt(val);
    public static ModInt operator +(ModInt a, int b) => new ModInt() { Data = (a.Data + b + POSITIVIZER) % MOD };
    public static ModInt operator +(ModInt a, long b) => new ModInt(a.Data + b);
    public static ModInt operator +(ModInt a, ModInt b) { long res = a.Data + b.Data; return new ModInt() { Data = res >= MOD ? res - MOD : res }; }
    public static ModInt operator -(ModInt a, int b) => new ModInt() { Data = (a.Data - b + POSITIVIZER) % MOD };
    public static ModInt operator -(ModInt a, long b) => new ModInt(a.Data - b);
    public static ModInt operator -(ModInt a, ModInt b) { long res = a.Data - b.Data; return new ModInt() { Data = res < 0 ? res + MOD : res }; }
    public static ModInt operator *(ModInt a, int b) => new ModInt(a.Data * b);
    public static ModInt operator *(ModInt a, long b) => a * new ModInt(b);
    public static ModInt operator *(ModInt a, ModInt b) => new ModInt() { Data = a.Data * b.Data % MOD };
    public static ModInt operator /(ModInt a, ModInt b) => new ModInt() { Data = a.Data * GetInverse(b) % MOD };
    public override string ToString() => Data.ToString();
    static long GetInverse(long a)
    {
        long div, p = MOD, x1 = 1, y1 = 0, x2 = 0, y2 = 1;
        while (true)
        {
            if (p == 1) return x2 + MOD; div = a / p; x1 -= x2 * div; y1 -= y2 * div; a %= p;
            if (a == 1) return x1 + MOD; div = p / a; x2 -= x1 * div; y2 -= y1 * div; p %= a;
        }
    }
}
0