結果

問題 No.3115 One Power One Kill
コンテスト
ユーザー kkk
提出日時 2025-04-20 19:16:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,831 bytes
コンパイル時間 4,731 ms
コンパイル使用メモリ 258,976 KB
実行使用メモリ 33,672 KB
平均クエリ数 2.00
最終ジャッジ日時 2025-04-20 19:16:13
合計ジャッジ時間 11,093 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /usr/include/c++/13/istream:41,
                 from /usr/include/c++/13/sstream:40,
                 from /usr/include/c++/13/complex:45,
                 from /usr/include/c++/13/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127,
                 from main.cpp:1:
In member function ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>]’,
    inlined from ‘int main()’ at main.cpp:199:11:
/usr/include/c++/13/ostream:204:25: warning: ‘A’ may be used uninitialized [-Wmaybe-uninitialized]
  204 |       { return _M_insert(__n); }
      |                ~~~~~~~~~^~~~~
main.cpp: In function ‘int main()’:
main.cpp:164:6: note: ‘A’ was declared here
  164 |   ll A, B;
      |      ^
main.cpp:195:7: warning: ‘B’ may be used uninitialized [-Wmaybe-uninitialized]
  195 |   mod = B;
      |   ~~~~^~~
main.cpp:164:9: note: ‘B’ was declared here
  164 |   ll A, B;
      |         ^

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace atcoder;
using namespace std;
using ll = long long;
// --------------------------------------------------------
template <class T>
bool chmax(T &a, const T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#define FOR(i, l, r) for (ll i = (l); i < (r); ++i)
#define RFOR(i, l, r) for (ll i = (r) - 1; (l) <= i; --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define MIN(c) *min_element(ALL(c))
#define MAX(c) *max_element(ALL(c))
#define SUM(c) accumulate(ALL(c), 0LL)
#define BITCNT(c) __builtin_popcountll(c)
#define SZ(c) ((int)(c).size())
#define COUT(c) cout << (c) << '\n'
#define debug(x) cerr << #x << " = " << (x) << '\n';
using P = pair<ll, ll>;
using VP = vector<P>;
using VVP = vector<VP>;
using VS = vector<string>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
static const double EPS = 1e-10;
static const double PI = acos(-1.0);
template <typename T>
void arrPrint(vector<T> arr) {
  for (auto v : arr) cout << v << " ";
  cout << '\n';
}
template <typename T>
void arrPrint2Dim(vector<vector<T>> arr) {
  for (auto a : arr) arrPrint(a);
}
template <typename T, typename T2>
void arrPrintPair(vector<pair<T, T2>> arr) {
  for (auto v : arr) cout << "{" << v.first << "," << v.second << "}, ";
  cout << '\n';
}
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

// static const int INF = (1 << 30) - 1;  // 1073741824 - 1
static const ll INF = (1LL << 62) - 1;  // 4611686018427387904 - 1
ll llceil(ll a, ll b) { return (a + b - 1) / b; }
using T = tuple<ll, ll, ll>;

bool isPrime(ll n) {  // is n prime or not
  if (n == 1) return false;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}

long long mod = 998244353;
struct mint {
 public:
  long long x;
  mint(long long x = 0) : x((mod + x) % mod) {}
  mint(std::string &s) {
    long long z = 0;
    for (int i = 0; i < SZ(s); i++) {
      z *= 10;
      z += s[i] - '0';
      z %= mod;
    }
    this->x = z;
  }
  mint &operator+=(const mint &a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator-=(const mint &a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint operator-() const {
    mint res(*this);
    return res * -1;
  }
  mint &operator*=(const mint &a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint &operator/=(const mint &a) {
    long long n = mod - 2;
    mint u = 1, b = a;
    while (n > 0) {
      if (n & 1) {
        u *= b;
      }
      b *= b;
      n >>= 1;
    }
    return *this *= u;
  }
  mint operator+(const mint &a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint &a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint &a) const {
    mint res(*this);
    return res *= a;
  }
  mint operator/(const mint &a) const {
    mint res(*this);
    return res /= a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  friend std::ostream &operator<<(std::ostream &os, const mint &n) {
    return os << n.x;
  }
  bool operator==(const mint &a) const { return this->x == a.x; }
  bool operator<(const mint &r) { return this->x < r.x; }
  bool operator<=(const mint &r) { return this->x <= r.x; }
  bool operator!=(const mint &r) { return this->x != r.x; }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  const ll mi = 100, mx = 100000;
  ll A, B;
  map<ll, ll> kToAns;
  auto labo = [&]() {
    RFOR(b, mi, mx + 1) {
      // if (!isPrime(b)) continue;
      mod = b;
      FOR(a, mi, mx + 1) {
        map<ll, ll> gcdToNewX;
        bool ok = true;
        ll y = mint(a).pow(b).x;
        RFOR(x, mi, mx + 1) {
          ll k = gcd(x, y);
          mint newX = mint(x).pow(a);
          if (gcdToNewX.count(k) && gcdToNewX[k] != newX.x) {
            ok = false;
            break;
          }
          gcdToNewX[k] = newX.x;
        }
        if (ok) {
          A = a;
          B = b;
          kToAns = gcdToNewX;
          return;
        }
      }
    }
  };
  labo();

  // 実験結果より、これはいけるらしい
  mod = B;

  ll k, result;

  cout << A << " " << B << endl;
  cin >> k;
  cout << kToAns[k] << endl;
  cin >> result;
}
0