結果

問題 No.3115 One Power One Kill
コンテスト
ユーザー hiromi_ayase
提出日時 2025-04-20 21:05:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 1,190 bytes
コンパイル時間 6,161 ms
コンパイル使用メモリ 333,480 KB
実行使用メモリ 25,996 KB
平均クエリ数 2.00
最終ジャッジ日時 2025-04-20 21:05:54
合計ジャッジ時間 9,418 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::tuple<long long int, long long int, std::map<long long int, long long int, std::less<long long int>, std::allocator<std::pair<const long long int, long long int> > > > search()’:
main.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
   53 | }
      | ^

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define FAST_IO                \
  ios::sync_with_stdio(false); \
  cin.tie(0);
const i64 INF = 1001001001001001001;
using Modint = atcoder::static_modint<1000000007>;

i64 pow(i64 X, i64 e, i64 m) {
  i64 res = 1;
  while (e > 0) {
    if (e & 1) {
      res = (res * X) % m;
    }
    X = (X * X) % m;
    e >>= 1;
  }
  return res;
}

tuple<i64, i64, map<i64, i64>> search() {
  for (i64 A = 100; A <= 1000; A ++) {
    for (i64 B = 100; B <= 1000; B ++) {
      i64 Y = pow(A, B, 1e9 + 7);

      bool ok = true;
      map<i64, i64> mp;

      for (i64 X = 1; X <= 100000; X ++) {
        i64 K = gcd(X, Y);
        i64 Xd = pow(X, A, B);
        if (mp.count(K) == 0) {
          mp[K] = Xd;
        } else {
          if (mp[K] != Xd) {
            ok = false;
            break;
          }
        }
      }
      if (ok) {
        return {A, B, mp};
      }
    }
  }

}

int main() {
  FAST_IO

  auto [A, B, mp] = search();


  cout << A << " " << B << endl;

  int K;
  cin >> K;


  cout << mp[K] << endl;

}
0