結果

問題 No.2558 中国剰余定理
ユーザー rrrriki
提出日時 2023-12-02 14:47:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 32 ms / 2,000 ms
コード長 9,272 bytes
コンパイル時間 4,194 ms
コンパイル使用メモリ 266,272 KB
最終ジャッジ日時 2025-02-18 03:56:44
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/**
* author: rrrriki
* created: 02.12.2023 14:43:36
*/
#define USE_ACL
#if !__INCLUDE_LEVEL__
#include __FILE__
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int A, B, a, b;
cin >> A >> B >> a >> b;
for (int i = 0; i < 1e9; i++) {
if (i % A == a && i % B == b) {
cout << i << "\n";
return 0;
}
}
return 0;
}
#else
// clang-format off
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define YES cout << "Yes\n"
#define NO cout << "No\n"
using namespace std;
#ifdef USE_ACL
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
//using mint = modint1000000007;
#endif
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 42
#endif
using ll = long long;
using vl = vector<ll>;
// outC(A);
template <class T> void out_c(T &A, string gap=" ") {auto itr = A.begin(); if (itr != A.end()) {cout << *itr; itr++;} while (itr != A.end()) {cout <<
    gap << *itr; itr++;}cout << "\n"; return;}
template <class T> void out_c_pairs(T &A, string gap_inside=" ", string gap_outside = " ") {auto itr = A.begin();if (itr != A.end()) {cout << itr
    ->first << gap_inside << itr->second;itr++;}while (itr != A.end()) {cout << gap_outside << itr->first << gap_inside << itr->second;itr++;}cout <<
    "\n";return;}
ll _pow(ll x, ll n) {if (n == 0) return 1; ll val = _pow(x, n / 2); val *= val; if (n & 1) val *= x; return val;} //
//
template <class T> T mnht(T a, T b, T c, T d) {return abs(a - c) + abs(b - d);}
//
void rle(string s, vector<pair<char, int>> &vec){int cnt = 1; for(int i = 1; i < (int)s.size(); i++) {if(s[i] != s[i-1]){vec.emplace_back(s[i-1], cnt
    ); cnt = 0;} cnt++;} vec.emplace_back(s.back(), cnt);}
//
bool is_prime(ll x){for (ll i=2; i*i<=x; i++){if(x%i==0)return false;}return true;}
map<ll,int> prime_factor(ll n) {map<ll,int> ret; for(ll i=2; i*i <= n; i++) {while(n%i == 0) {ret[i]++; n /= i;}} if(n != 1) ret[n]=1;return ret;}
//
template <typename T> bool next_combination(const T first, const T last, int k) {
const T subset = first + k;
// empty container | k = 0 | k == n
if (first == last || first == subset || last == subset) {
return false;
}
T src = subset;
while (first != src) {
src--;
if (*src < *(last - 1)) {
T dest = subset;
while (*src >= *dest) {
dest++;
}
iter_swap(src, dest);
rotate(src + 1, dest + 1, last);
rotate(subset, subset + (last - dest) - 1, last);
return true;
}
}
// restore
rotate(first, subset, last);
return false;
}
//
/**
* @brief Edge
*
* @tparam T int
*/
template <typename T = int> struct Edge {
int from, to; //
T cost; //
int idx; //
//
Edge() = default;
//
bool operator<(const Edge &other) const { return cost < other.cost; }
bool operator>(const Edge& other) const { return cost > other.cost; }
friend std::ostream& operator<<(std::ostream& os, const Edge& edge) { os << edge.to; return os; }
//
Edge(int from, int to, T cost = 1, int idx = -1)
: from(from), to(to), cost(cost), idx(idx) {}
// int
operator int() const { return to; }
};
/**
* @brief Graph
*
* @tparam T int
*/
template <typename T = int> struct Graph {
vector<vector<Edge<T>>> g; //
int es; //
//
Graph() = default;
// n
explicit Graph(int n) : g(n), es(0) {}
//
size_t size() const { return g.size(); }
//
void add_directed_edge(int from, int to, T cost = 1) {
g[from].emplace_back(from, to, cost, es++);
}
//
void add_edge(int from, int to, T cost = 1) {
g[from].emplace_back(from, to, cost, es);
g[to].emplace_back(to, from, cost, es++);
}
//
// M: , padding: , weighted: , directed:
void read(int M, int padding = -1, bool weighted = false,
bool directed = false) {
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
a += padding;
b += padding;
T c = T(1);
if (weighted) cin >> c;
if (directed)
add_directed_edge(a, b, c);
else
add_edge(a, b, c);
}
}
//
inline vector<Edge<T>> &operator[](const int &k) { return g[k]; }
// const
inline const vector<Edge<T>> &operator[](const int &k) const { return g[k]; }
};
// Edges
template <typename T = int> using Edges = vector<Edge<T>>;
/**
* @brief NQueenN-Queen
*
*/
struct NQueen {
public:
explicit NQueen(int n) : N(n) { assert(n > 0);}
bool add_queen(int x, int y) { //
if (row.count(x) || col.count(y) || diag1.count(x + y) || diag2.count(x - y)) return false;
assert(x < N && y < N);
assert(x >= 0 && y >= 0);
queens.emplace(x, y);
row.insert(x); // x
col.insert(y); // y
diag1.insert(x + y); // x + y
diag2.insert(x - y); // x - y
return true;
}
bool remove_queen(int x, int y) { //
if (!row.count(x) || !col.count(y) || !diag1.count(x + y) || !diag2.count(x - y)) return false;
assert(x < N && y < N);
assert(x >= 0 && y >= 0);
queens.erase({x, y});
if (added_queens.count({x, y})) added_queens.erase({x, y});
row.erase(x);
col.erase(y);
diag1.erase(x + y);
diag2.erase(x - y);
return true;
}
// x, y
bool is_valid(int x, int y) { return !row.count(x) && !col.count(y) && !diag1.count(x + y) && !diag2.count(x - y);}
//
bool is_valid() { return (int)row.size() == N;}
bool solve(int x = 0) { // x
if (x == N) return true;
if (is_valid()) return true;
if (row.count(x)) return solve(x + 1);
for (int y = 0; y < N; y++) {
if (is_valid(x, y)) {
add_queen(x, y);
added_queens.emplace(x, y);
if (solve(x + 1)) return true;
added_queens.erase({x, y});
remove_queen(x, y);
}
}
return false;
}
int size() { return N; } //
friend std::ostream& operator<<(std::ostream& os, const NQueen& nqueen) { //
for (auto [x, y] : nqueen.queens) os << x << " " << y << "\n";
return os;
}
// vector<pair<int,int>>
vector<pair<int, int> > get_queens() { return vector<pair<int, int> >(queens.begin(), queens.end());}
// vector<pair<int,int>>
vector<pair<int, int> > get_added_queens() { return vector<pair<int, int> >(added_queens.begin(), added_queens.end());}
void print(char c = 'Q', char d = '.') { //
vector<vector<char> > board(N, vector<char>(N, d));
for (auto [x, y] : queens) {
board[x][y] = c;
}
for (auto& row : board) {
for (auto& c : row) {
cout << c;
}
cout << "\n";
}
}
private:
int N; //
unordered_set<int> row, col, diag1, diag2; //
set<pair<int, int> > queens; //
set<pair<int, int> > added_queens; //
};
// clang-format on
#endif
/*
******* *******
******* *******
******* *******
******* *******
******* *******
******* *******
******* *******
******* *******
******* *******
******* *******
******* *******
******* *******
******* *******
******* *******
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0