#define PROBLEM "https://yukicoder.me/problems/no/438" #include #include #include #include class EuclideanAlgorithm { using T = long long; // 大きすぎるとオーバーフローしてしまう const static inline T m_mx = 1e9; const T m_a; const T m_b; const T m_c; T m_gcd; T m_x; T m_y; auto excludedEuclidAlgorithm(T a, T b) -> std::tuple { if(a < 0) { auto [g, x, y] = excludedEuclidAlgorithm(-a, -b); return {g,-x,-y}; } if(b == 0) { return {a, 1, 0}; } auto [g, y, x] = excludedEuclidAlgorithm(b, a % b); y -= a / b * x; return {g, x, y}; } auto kRange(T x, T b, T l) const -> std::pair { // x + b * k >= l を満たす k の範囲を求める T xd = (l - x); if(b == 0 && x >= l) { return {-m_mx,m_mx}; } if(b == 0 && x < l) { return {m_mx,-m_mx}; } if(b > 0 && xd < 0) { return {xd / b,m_mx}; } if(b > 0 && xd >= 0) { return {(xd + b - 1) / b,m_mx}; } if(b < 0 && xd < 0) { return {-m_mx,(-xd) / (-b)}; } if(b < 0 && xd >= 0) { return {-m_mx,-(xd - b - 1) / (-b)}; } return {m_mx,-m_mx}; } public: auto debug()const { std::cout << m_a << " * " << m_x << " + " << m_b << " * " << m_y << " = " << m_c << std::endl; std::cout << "calc: " << m_a * m_x + m_b * m_y << " = " << m_c << std::endl; } EuclideanAlgorithm(T a, T b, T c) :m_a(a), m_b(b), m_c(c) { if(a == 0 && b == 0) { throw std::runtime_error(""); } auto [g, x, y] = excludedEuclidAlgorithm(a, b); if(c % g > 0) { throw std::runtime_error("There is no solution to the equation. c must be divisible by gcd(a,b)."); } m_gcd = g; m_x = c / g * x; m_y = c / g * y; } EuclideanAlgorithm(T a, T b) :EuclideanAlgorithm(a, b, std::gcd(a, b)) {} auto gcd() const { return m_gcd; } auto get(T x, T y) const { return m_a * x + m_b * y; } auto get(T k) const ->std::pair { if(m_b == 0) { return {m_x,m_y - k}; } if(m_a == 0) { return {m_x + k,m_y}; } return {m_x + m_b * k, m_y - m_a * k}; } auto getMinX(T x_l = 0)const -> std::pair { return kRange(m_x, m_b, x_l); } auto getMinY(T y_l = 0)const -> std::pair { return kRange(m_y, -1 * m_a, y_l); } auto getMin(T x_l = 0, T y_l = 0)const -> std::pair { auto [xl, xr] = getMinX(x_l); auto [yl, yr] = getMinY(y_l); return {std::max(xl,yl),std::min(xr,yr)}; } }; using ll = long long; using std::cout; using std::cin; constexpr char endl = '\n'; struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing; auto conv(ll a, ll b, char ac = 'c', char bc = 'w') ->std::string { if(2 * (std::abs(a) + std::abs(b)) - 1 > 10000) { return "NO"; } if(a <= 0) { return conv(b, a, bc, ac); } std::string ret = ""; ret += std::string(std::abs(b), bc); ret += std::string(a, ac); ret += std::string(a - 1, 'C'); ret += (b > 0) ? std::string(b, 'C') : std::string(-b, 'W'); return ret; } signed main() { ll x, y, z; cin >> x >> y >> z; if(z == 0) { cout << "ccW" << endl; return 0; } if(z % std::gcd(x, y) > 0) { cout << "NO" << endl; return 0; } auto ea = EuclideanAlgorithm(x, y, z); auto [kl, kr] = ea.getMin(); ll ka = 0, kb = 0, sum = 1e18; for(int k = kl - 10; k <= kl + 10; ++k) { auto [a, b] = ea.get(k); auto s = std::abs(a) + std::abs(b); if(s < sum) { sum = s; ka = a; kb = b; } } for(int k = kr - 10; k <= kr + 10; ++k) { auto [a, b] = ea.get(k); auto s = std::abs(a) + std::abs(b); if(s < sum) { sum = s; ka = a; kb = b; } } auto ans = conv(ka, kb); cout << ans << endl; }