結果

問題 No.3133 法B逆元
コンテスト
ユーザー 👑 p-adic
提出日時 2024-02-18 20:35:52
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 868 bytes
コンパイル時間 4,248 ms
コンパイル使用メモリ 207,520 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-02 20:50:16
合計ジャッジ時間 4,950 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
int main()
{
  unsigned long long N; cin >> N;
  unsigned int B; cin >> B;
  unsigned int euler = B;
  unsigned int B_copy = B;
  for( unsigned int i = 2 ; i * i <= B_copy ; i++ ){
    if( B_copy % i == 0 ){
      euler /= i;
      euler *= i - 1;
      B_copy /= i;
      while( B_copy % i == 0 ){
	B_copy /= i;
      }
    }
  }
  if( B_copy != 1 ){
    euler /= B_copy;
    euler *= B_copy - 1;
  }
  N %= B;
  unsigned int exponent = euler - 1;
  unsigned long long power_N = 1 % B;
  unsigned long long power_power_N = N;
  while( exponent > 0 ){
    if( exponent % 2 == 1 ){
      power_N *= power_power_N;
      power_N %= B;
    }
    power_power_N *= power_power_N;
    power_power_N %= B;
    exponent /= 2;
  }
  if( power_N * N % B == 1 % B ){
    cout << power_N << "\n";
  } else {
    cout << "NaN\n";
  }
}
0