結果
| 問題 | No.2260 Adic Sum |
| ユーザー |
 AC2K
|
| 提出日時 | 2024-10-05 09:07:58 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 22,335 bytes |
| コンパイル時間 | 3,147 ms |
| コンパイル使用メモリ | 252,440 KB |
| 実行使用メモリ | 8,980 KB |
| 最終ジャッジ日時 | 2024-10-05 09:08:06 |
| 合計ジャッジ時間 | 7,162 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,820 KB |
| testcase_01 | AC | 2 ms
6,816 KB |
| testcase_02 | AC | 1 ms
6,820 KB |
| testcase_03 | AC | 1 ms
6,816 KB |
| testcase_04 | AC | 1 ms
6,816 KB |
| testcase_05 | AC | 1 ms
6,820 KB |
| testcase_06 | AC | 2 ms
6,820 KB |
| testcase_07 | AC | 1 ms
6,820 KB |
| testcase_08 | AC | 5 ms
6,816 KB |
| testcase_09 | AC | 2 ms
6,816 KB |
| testcase_10 | AC | 2 ms
6,820 KB |
| testcase_11 | AC | 1 ms
6,816 KB |
| testcase_12 | AC | 3 ms
6,816 KB |
| testcase_13 | AC | 2 ms
6,820 KB |
| testcase_14 | WA | - |
| testcase_15 | AC | 14 ms
6,816 KB |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | AC | 161 ms
8,756 KB |
| testcase_19 | AC | 175 ms
8,784 KB |
| testcase_20 | AC | 116 ms
8,900 KB |
| testcase_21 | AC | 122 ms
8,904 KB |
| testcase_22 | AC | 101 ms
8,896 KB |
| testcase_23 | WA | - |
| testcase_24 | AC | 165 ms
8,788 KB |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | AC | 19 ms
6,816 KB |
| testcase_31 | AC | 48 ms
6,820 KB |
| testcase_32 | AC | 48 ms
6,816 KB |
| testcase_33 | AC | 36 ms
8,336 KB |
| testcase_34 | AC | 50 ms
8,204 KB |
| testcase_35 | AC | 281 ms
8,788 KB |
ソースコード
#line 1 "Library/src/debug.hpp"
#ifdef ONLINE_JUDGE
#define debug(x) void(0)
#else
#define _GLIBCXX_DEBUG
#define debug(x) std::cerr << __LINE__ << " : " << #x << " = " << (x) << std::endl
#endif
/**
* @brief Debugger
*/
#line 2 "Library/src/math/rho.hpp"
#include <algorithm>
#include <vector>
#line 2 "Library/src/math/gcd.hpp"
#include <cassert>
#include <cmath>
#include <tuple>
namespace kyopro {
template <typename T> constexpr inline T _gcd(T a, T b) noexcept {
assert(a >= 0 && b >= 0);
if (a == 0 || b == 0) return a + b;
int d = std::min<T>(__builtin_ctzll(a), __builtin_ctzll(b));
a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b);
while (a != b) {
if (!a || !b) {
return a + b;
}
if (a >= b) {
a -= b;
a >>= __builtin_ctzll(a);
} else {
b -= a;
b >>= __builtin_ctzll(b);
}
}
return a << d;
}
template <typename T>
constexpr inline T ext_gcd(T a, T b, T& x, T& y) noexcept {
x = 1, y = 0;
T nx = 0, ny = 1;
while (b) {
T q = a / b;
std::tie(a, b) = std::pair<T, T>{b, a % b};
std::tie(x, nx) = std::pair<T, T>{nx, x - nx * q};
std::tie(y, ny) = std::pair<T, T>{ny, y - ny * q};
}
return a;
}
}; // namespace kyopro
/**
* @brief gcd
*/
#line 3 "Library/src/math/dynamic_modint.hpp"
#include <iostream>
#line 2 "Library/src/internal/barrett.hpp"
#include <cstdint>
namespace kyopro {
namespace internal {
class barrett {
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
u32 m;
u64 im;
public:
constexpr barrett() : m(0), im(0) {}
constexpr barrett(u32 m)
: m(m), im(static_cast<u64>(-1) / m + 1) {}
constexpr u32 get_mod() const { return m; }
constexpr u32 reduce(u32 a) const { return mul(1, a); }
constexpr u32 mul(u32 a, u32 b) const {
u64 z = (u64)a * b;
u64 x = (u64)(((u128)(z)*im) >> 64);
u64 y = x * m;
return (u32)(z - y + (z < y ? m : 0));
}
};
}; // namespace internal
}; // namespace kyopro
/**
* @brief Barrett Reduction
* @see https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp
*/
#line 3 "Library/src/internal/montgomery.hpp"
#include <limits>
#include <numeric>
#line 5 "Library/src/internal/type_traits.hpp"
#include <typeinfo>
#line 7 "Library/src/internal/type_traits.hpp"
namespace kyopro {
namespace internal {
template <typename... Args> struct first_enabled {};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
: first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
using type = T;
};
template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;
template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least {
using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>,
std::enable_if<dgt <= 16, std::int16_t>,
std::enable_if<dgt <= 32, std::int32_t>,
std::enable_if<dgt <= 64, std::int64_t>,
std::enable_if<dgt <= 128, __int128_t>>;
};
template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least {
using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>,
std::enable_if<dgt <= 16, std::uint16_t>,
std::enable_if<dgt <= 32, std::uint32_t>,
std::enable_if<dgt <= 64, std::uint64_t>,
std::enable_if<dgt <= 128, __uint128_t>>;
};
template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;
template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;
template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;
struct modint_base {};
template <typename T> using is_modint = std::is_base_of<modint_base, T>;
template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
// is_integral
template <typename T>
using is_integral_t =
std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||
std::is_same_v<T, __uint128_t>>;
}; // namespace internal
}; // namespace kyopro
/**
* @brief Type Traits
* @see https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
*/
#line 6 "Library/src/internal/montgomery.hpp"
namespace kyopro {
namespace internal {
using u32 = uint32_t;
using u64 = uint64_t;
using i32 = int32_t;
using i64 = int64_t;
using u128 = __uint128_t;
using i128 = __int128_t;
template <typename T> class Montgomery {
static constexpr int lg = std::numeric_limits<T>::digits;
using LargeT = internal::double_size_uint_t<T>;
T mod, r, r2, minv;
T inv() {
T t = 0, res = 0;
for (int i = 0; i < lg; ++i) {
if (~t & 1) {
t += mod;
res += static_cast<T>(1) << i;
}
t >>= 1;
}
return res;
}
public:
Montgomery() = default;
constexpr T get_mod() { return mod; }
void set_mod(T m) {
assert(m);
assert(m & 1);
mod = m;
r = (-static_cast<T>(mod)) % mod;
r2 = (-static_cast<LargeT>(mod)) % mod;
minv = inv();
}
T reduce(LargeT x) const {
u64 res =
(x + static_cast<LargeT>(static_cast<T>(x) * minv) * mod) >> lg;
if (res >= mod) res -= mod;
return res;
}
T generate(LargeT x) { return reduce(x * r2); }
T mul(T x, T y) { return reduce((LargeT)x * y); }
};
}; // namespace internal
}; // namespace kyopro
/**
* @brief Montgomery Reduction
*/
#line 6 "Library/src/math/dynamic_modint.hpp"
namespace kyopro {
template <int id = -1> class barrett_modint : internal::modint_base {
using mint = barrett_modint<id>;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using br = internal::barrett;
static br brt;
u32 v;
public:
static void set_mod(u32 mod_) { brt = br(mod_); }
public:
explicit constexpr barrett_modint() noexcept : v(0) { assert(mod()); }
explicit constexpr barrett_modint(i64 v_) noexcept : v() {
assert(mod());
if (v_ < 0) v_ = (i64)mod() - v_;
v = brt.reduce(v_);
}
u32 val() const noexcept { return v; }
static u32 mod() { return brt.get_mod(); }
static mint raw(u32 v) {
mint x;
x.v = v;
return x;
}
constexpr mint& operator++() noexcept {
++v;
if (v == mod()) v = 0;
return (*this);
}
constexpr mint& operator--() noexcept {
if (v == 0) v = mod();
--v;
return (*this);
}
constexpr mint operator++(int) noexcept {
mint res(*this);
++(*this);
return res;
}
constexpr mint operator--(int) noexcept {
mint res(*this);
--(*this);
return res;
}
constexpr mint& operator+=(const mint& r) noexcept {
v += r.v;
if (v >= mod()) v -= mod();
return (*this);
}
constexpr mint& operator-=(const mint& r) noexcept {
v += mod() - r.v;
if (v >= mod()) {
v -= mod();
}
return (*this);
}
constexpr mint& operator*=(const mint& r) noexcept {
v = brt.mul(v, r.v);
return (*this);
}
constexpr mint& operator/=(const mint& r) noexcept {
return (*this) *= r.inv();
}
friend mint operator+(const mint& lhs, const mint& rhs) noexcept {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) noexcept {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) noexcept {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) noexcept {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) noexcept {
return lhs.v == rhs.v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) noexcept {
return lhs.v != rhs.v;
}
constexpr mint& operator+=(i64 r) noexcept { return (*this) += mint(r); }
constexpr mint& operator-=(i64 r) noexcept { return (*this) -= mint(r); }
constexpr mint& operator*=(i64 r) noexcept { return (*this) *= mint(r); }
friend mint operator+(i64 l, const mint& r) noexcept {
return mint(l) += r;
}
friend mint operator+(const mint& l, i64 r) noexcept {
return mint(l) += r;
}
friend mint operator-(i64 l, const mint& r) noexcept {
return mint(l) -= r;
}
friend mint operator-(const mint& l, i64 r) noexcept {
return mint(l) -= r;
}
friend mint operator*(i64 l, const mint& r) noexcept {
return mint(l) *= r;
}
friend mint operator*(const mint& l, i64 r) noexcept {
return mint(l) *= r;
}
constexpr mint operator+() const noexcept { return *this; }
constexpr mint operator-() const noexcept { return mint() - *this; }
template <typename T> mint pow(T e) const noexcept {
mint res(1), base(*this);
while (e) {
if (e & 1) {
res *= base;
}
e >>= 1;
base *= base;
}
return res;
}
constexpr mint inv() const noexcept { return pow(mod() - 2); }
};
}; // namespace kyopro
template <int id>
typename kyopro::barrett_modint<id>::br kyopro::barrett_modint<id>::brt;
namespace kyopro {
template <typename T, int id = -1>
class montgomery_modint : internal::modint_base {
using LargeT = internal::double_size_uint_t<T>;
static T _mod;
static internal::Montgomery<T> mr;
public:
static void set_mod(T mod_) {
mr.set_mod(mod_);
_mod = mod_;
}
static T mod() { return _mod; }
private:
T v;
public:
montgomery_modint(T v_ = 0) {
assert(_mod);
v = mr.generate(v_);
}
T val() const { return mr.reduce(v); }
using mint = montgomery_modint<T, id>;
mint& operator+=(const mint& r) {
v += r.v;
if (v >= mr.get_mod()) {
v -= mr.get_mod();
}
return (*this);
}
mint& operator-=(const mint& r) {
v += mr.get_mod() - r.v;
if (v >= mr.get_mod) {
v -= mr.get_mod();
}
return (*this);
}
mint& operator*=(const mint& r) {
v = mr.mul(v, r.v);
return (*this);
}
mint operator+(const mint& r) { return mint(*this) += r; }
mint operator-(const mint& r) { return mint(*this) -= r; }
mint operator*(const mint& r) { return mint(*this) *= r; }
mint& operator=(const T& v_) {
(*this) = mint(v_);
return (*this);
}
friend std::ostream& operator<<(std::ostream& os, const mint& mt) {
os << mt.val();
return os;
}
friend std::istream& operator>>(std::istream& is, mint& mt) {
T v_;
is >> v_;
mt = v_;
return is;
}
template <typename P> mint pow(P e) const {
assert(e >= 0);
mint res(1), base(*this);
while (e) {
if (e & 1) {
res *= base;
}
e >>= 1;
base *= base;
}
return res;
}
mint inv() const { return pow(mod() - 2); }
mint& operator/=(const mint& r) { return (*this) *= r.inv(); }
mint operator/(const mint& r) const { return mint(*this) *= r.inv(); }
mint& operator/=(T r) { return (*this) /= mint(r); }
friend mint operator/(const mint& l, T r) { return mint(l) /= r; }
friend mint operator/(T l, const mint& r) { return mint(l) /= r; }
};
}; // namespace kyopro
template <typename T, int id> T kyopro::montgomery_modint<T, id>::_mod;
template <typename T, int id>
kyopro::internal::Montgomery<T> kyopro::montgomery_modint<T, id>::mr;
/**
* @brief Dynamic modint
*/
#line 3 "Library/src/math/miller.hpp"
namespace kyopro {
class miller {
using i128 = __int128_t;
using u128 = __uint128_t;
using u64 = std::uint64_t;
using u32 = std::uint32_t;
template <typename T, typename mint, const int bases[], int length>
static constexpr bool miller_rabin(T n) {
T d = n - 1;
while (~d & 1) {
d >>= 1;
}
const T rev = n - 1;
if (mint::mod() != n) {
mint::set_mod(n);
}
for (int i = 0; i < length; ++i) {
if (n <= bases[i]) {
return true;
}
T t = d;
mint y = mint(bases[i]).pow(t);
while (t != n - 1 && y.val() != 1 && y.val() != rev) {
y *= y;
t <<= 1;
}
if (y.val() != rev && (~t & 1)) return false;
}
return true;
}
// 底
static constexpr int bases_int[3] = {2, 7, 61};
static constexpr int bases_ll[7] = {2, 325, 9375, 28178,
450775, 9780504, 1795265022};
public:
template <typename T> static constexpr bool is_prime(T n) {
if (n < 2) {
return false;
} else if (n == 2) {
return true;
} else if (~n & 1) {
return false;
};
if constexpr (std::numeric_limits<T>::digits < 32) {
return miller_rabin<T, montgomery_modint<std::make_unsigned_t<T>>,
bases_int, 3>(n);
} else {
if (n <= 1 << 30)
return miller_rabin<T,
montgomery_modint<std::make_unsigned_t<T>>,
bases_int, 3>(n);
else
return miller_rabin<
T, montgomery_modint<std::make_unsigned_t<T>>, bases_ll, 7>(
n);
}
return false;
}
};
}; // namespace kyopro
/**
* @brief Primality Test(MillerRabin素数判定)
* @docs docs/math/miller.md
*/
#line 2 "Library/src/random/xor_shift.hpp"
#include <chrono>
#line 4 "Library/src/random/xor_shift.hpp"
#include <random>
namespace kyopro {
struct xor_shift32 {
uint32_t rng;
constexpr explicit xor_shift32(uint32_t seed) : rng(seed) {}
explicit xor_shift32()
: rng(std::chrono::steady_clock::now().time_since_epoch().count()) {}
constexpr uint32_t operator()() {
rng ^= rng << 13;
rng ^= rng >> 17;
rng ^= rng << 5;
return rng;
}
};
struct xor_shift {
uint64_t rng;
constexpr explicit xor_shift(uint64_t seed) : rng(seed) {}
explicit xor_shift()
: rng(std::chrono::steady_clock::now().time_since_epoch().count()) {}
constexpr uint64_t operator()() {
rng ^= rng << 13;
rng ^= rng >> 7;
rng ^= rng << 17;
return rng;
}
};
}; // namespace kyopro
/**
* @brief Xor Shift
*/
#line 7 "Library/src/math/rho.hpp"
namespace kyopro {
class rho {
using i128 = __int128_t;
using u128 = __uint128_t;
using u64 = uint64_t;
using u32 = uint32_t;
template <typename T,typename mint> static constexpr T find_factor(T n) {
xor_shift32 rng(2023);
if (~n & 1uL) {
return 2;
}
if (kyopro::miller::is_prime(n)) {
return n;
}
if (mint::mod() != n) {
mint::set_mod(n);
}
while (1) {
T c = rng();
const auto f = [&](mint x) -> mint { return x * x + c; };
mint x = rng();
mint y = f(x);
T d = 1;
while (d == 1) {
d = _gcd<std::make_signed_t<T>>(
std::abs((std::make_signed_t<T>)x.val() - (std::make_signed_t<T>)y.val()), n);
x = f(x);
y = f(f(y));
}
if (1 < d && d < n) {
return d;
}
}
exit(-1);
}
template <typename T,typename mint> static std::vector<T> rho_fact(T n) {
if (n < 2) {
return {};
}
if (kyopro::miller::is_prime(n)) {
return {n};
}
std::vector<T> v;
std::vector<T> st{n};
while (!st.empty()) {
u64 m = st.back();
if (kyopro::miller::is_prime(m)) {
v.emplace_back(m);
st.pop_back();
} else {
T d = find_factor<T, mint>(m);
st.back() /= d;
st.emplace_back(d);
}
}
return v;
}
public:
template <typename T> static std::vector<T> factorize(T n) {
if (n < 2) {
return {};
}
if constexpr (std::numeric_limits<T>::digits < 32) {
std::vector v = rho_fact<T, montgomery_modint<u32>>(n);
std::sort(v.begin(), v.end());
return v;
} else {
std::vector v = rho_fact<T, montgomery_modint<u64>>(n);
std::sort(v.begin(), v.end());
return v;
}
}
template<typename T>
static std::vector<std::pair<T, int>> exp_factorize(T n) {
std::vector pf = factorize(n);
if (pf.empty()) {
return {};
}
std::vector<std::pair<T, int>> res;
res.emplace_back(pf.front(), 1);
for (int i = 1; i < (int)pf.size(); i++) {
if (res.back().first == pf[i]) {
res.back().second++;
} else {
res.emplace_back(pf[i], 1);
}
}
return res;
}
template<typename T>
static std::vector<T> enumerate_divisor(T n) {
std::vector<std::pair<T, int>> pf = rho::exp_factorize(n);
std::vector<T> divisor{1};
for (auto [p, e] : pf) {
u64 pow = p;
int sz = divisor.size();
for (int i = 0; i < e; ++i) {
for (int j = 0; j < sz; ++j)
divisor.emplace_back(divisor[j] * pow);
pow *= p;
}
}
return divisor;
}
};
}; // namespace kyopro
/**
* @brief PollardRho素因数分解
* @docs docs/math/rho.md
*/
#line 2 "Library/src/stream.hpp"
#include <ctype.h>
#include <stdio.h>
#include <string>
#line 6 "Library/src/stream.hpp"
namespace kyopro {
inline void single_read(char& c) {
c = getchar_unlocked();
while (isspace(c)) c = getchar_unlocked();
}
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_read(T& a) {
a = 0;
bool is_negative = false;
char c = getchar_unlocked();
while (isspace(c)) {
c = getchar_unlocked();
}
if (c == '-') is_negative = true, c = getchar_unlocked();
while (isdigit(c)) {
a = 10 * a + (c - '0');
c = getchar_unlocked();
}
if (is_negative) a *= -1;
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_read(T& a) {
long long x;
single_read(x);
a = T(x);
}
inline void single_read(std::string& str) noexcept {
char c = getchar_unlocked();
while (isspace(c)) c = getchar_unlocked();
while (!isspace(c)) {
str += c;
c = getchar_unlocked();
}
}
template<typename T>
inline void read(T& x) noexcept {single_read(x);}
template <typename Head, typename... Tail>
inline void read(Head& head, Tail&... tail) noexcept {
single_read(head), read(tail...);
}
inline void single_write(char c) noexcept { putchar_unlocked(c); }
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_write(T a) noexcept {
if (!a) {
putchar_unlocked('0');
return;
}
if constexpr (std::is_signed_v<T>) {
if (a < 0) putchar_unlocked('-'), a *= -1;
}
constexpr int d = std::numeric_limits<T>::digits10;
char s[d + 1];
int now = d + 1;
while (a) {
s[--now] = (char)'0' + a % 10;
a /= 10;
}
while (now <= d) putchar_unlocked(s[now++]);
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_write(T a) noexcept {
single_write(a.val());
}
inline void single_write(const std::string& str) noexcept {
for (auto c : str) {
putchar_unlocked(c);
}
}
template <typename T> inline void write(T x) noexcept { single_write(x); }
template <typename Head, typename... Tail>
inline void write(Head head, Tail... tail) noexcept {
single_write(head);
putchar_unlocked(' ');
write(tail...);
}
template <typename... Args> inline void put(Args... x) noexcept {
write(x...);
putchar_unlocked('\n');
}
}; // namespace kyopro
/**
* @brief Fast IO(高速入出力)
*/
#line 2 "Library/src/template.hpp"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) std::begin(x), std::end(x)
#define popcount(x) __builtin_popcountll(x)
using i128 = __int128_t;
using ll = long long;
using ld = long double;
using graph = std::vector<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infl = std::numeric_limits<ll>::max() / 2;
const long double pi = acosl(-1);
constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {
return a < b && (a = b, true);
}
template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) {
return a > b && (a = b, true);
}
/**
* @brief Template
*/
#line 5 "a.cpp"
using namespace std;
using namespace kyopro;
int main() {
int n, p;
read(n, p);
vector<int> a(n);
rep(i, n) read(a[i]);
ll ans = 0;
for (int q = p; q <= (int)1e9; q *= p) {
unordered_map<int, int> rem;
rep(i, n)++ rem[a[i] % q];
for (auto [r, c] : rem) ans += (ll)c * (c - 1) / 2;
}
put(ans);
}