結果
| 問題 | No.981 一般冪乗根 |
| ユーザー |
 keymoon
|
| 提出日時 | 2020-01-28 22:38:06 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,931 bytes |
| コンパイル時間 | 1,052 ms |
| コンパイル使用メモリ | 111,616 KB |
| 実行使用メモリ | 23,040 KB |
| 最終ジャッジ日時 | 2024-10-09 14:03:27 |
| 合計ジャッジ時間 | 43,029 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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.
ソースコード
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);
Assert(aIndex != 0);
//これによって、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)
{
if (a == 1) return 0;
long mulOrder = ModInt.Mod - 1;
int tryCount = 1;
var curG = g;
while (true)
{
//Console.WriteLine($"Initializing {tryCount}th attempt...");
ModInt x = 1;
long xAInd = 0;
long xGInd = 0;
ModInt waiting = 1;
long waitingAInd = 0;
long waitingGInd = 0;
int step = 9;
while (true)
{
for (int i = 0; i < step; i += 3)
{
x *= curG; xGInd += tryCount;
//Console.WriteLine($"x = {x} = a^{xAInd} * g^{xGInd}");
if (x == waiting) goto found;
x *= x; xAInd = (xAInd << 1) % mulOrder; xGInd = (xGInd << 1) % mulOrder;
//Console.WriteLine($"x = {x} = a^{xAInd} * g^{xGInd}");
if (x == waiting) goto found;
x *= a; xAInd++;
//Console.WriteLine($"x = {x} = a^{xAInd} * g^{xGInd}");
if (x == waiting) goto found;
}
step <<= 1;
waiting = x;
waitingAInd = xAInd;
waitingGInd = xGInd;
}
found:;
//Console.WriteLine("Loop found.");
var aInd = (xAInd - waitingAInd + mulOrder) % mulOrder;
var gInd = (waitingGInd - xGInd + mulOrder) % mulOrder;
if (aInd == 0 || gInd == 0) { /*Console.WriteLine("failed.");*/ curG *= g; tryCount++; continue; }
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;
}
}
}