Submission #74367592
Source Code Expand
#include <cstdint>
#include <climits>
#include <type_traits>
#include <algorithm>
#include <cassert>
namespace dmodint_nm {
static_assert(CHAR_BIT == 8 && sizeof(unsigned) == 4 && sizeof(unsigned long long) == 8, "not support env.");
template <typename _Tp>
constexpr _Tp max_v = _Tp(-1) < _Tp(0)? ((_Tp(1) << (sizeof(_Tp) * 8 - 2)) - 1) * 2 + 1 : _Tp(-1);
template <typename _Tp>
constexpr bool is_uint_v = _Tp(-1) > _Tp(0);
#if __cplusplus >= 201703L
#define IF_CONSTEXPR(cond) if constexpr (cond)
#else
#define IF_CONSTEXPR(cond) if (false)
#endif
template <typename _log_t, typename _Tp_>
constexpr _log_t lg(_Tp_ n){ // log_2(n)
static_assert(is_uint_v<_Tp_>, "must be unsigned.");
static_assert(max_v<_log_t> >= sizeof(_Tp_) << 3, "too small.");
IF_CONSTEXPR (sizeof(_Tp_) <= 4)return 31 - __builtin_clz(n);
else IF_CONSTEXPR (sizeof(_Tp_) <= 8)return 63 - __builtin_clzll(n);
else {
static_assert(sizeof(_Tp_) <= 16, "too large.");
return n >> 64? 127 - __builtin_clzll(n >> 64) : 63 - __builtin_clzll(n);
}
}
template <typename _mod_t_, typename _dividend_t_, typename _log_t_, typename _reg_t_, typename _tmp_t_, typename _quot_t_>
struct barrett_reduce_basic {
typedef _mod_t_ mod_t;
typedef _dividend_t_ dividend_t;
typedef _log_t_ log_t;
typedef _reg_t_ reg_t;
typedef _tmp_t_ tmp_t;
typedef _quot_t_ quot_t;
typedef mod_t rem_t;
static_assert(is_uint_v<mod_t> && is_uint_v<dividend_t> &&
is_uint_v<log_t> && is_uint_v<reg_t> && is_uint_v<tmp_t>, "must be unsigned.");
mod_t mod;
dividend_t n; // dividend <= n
log_t k; // 2^k > n(mod-1)
reg_t I;
constexpr barrett_reduce_basic(mod_t __mod = 1, dividend_t __dvlm = max_v<dividend_t> >> 1)
: mod(__mod), n(__dvlm), k(), I() {
if (mod == 0)throw "mod = 0.";
if (mod == 1){mod = 1;I = 1, k = 0;return;}
if (n > max_v<tmp_t> / (mod - 1))throw "tmp_t too small.";
k = lg<log_t, tmp_t>(tmp_t(n) * (mod - 1)) + 1;
if (k > sizeof(tmp_t) << 3)throw "log_t too small.";
tmp_t t = k == sizeof(tmp_t) << 3? tmp_t(-1) / mod + 1 : ((tmp_t(1) << k) - 1) / mod + 1;
if (t > max_v<reg_t>)throw "reg_t too small.";
I = t;
if (n > max_v<tmp_t> / I)throw "tmp_t too small.";
if (tmp_t(n) * I >> k > max_v<quot_t>)throw "quot_t too small.";
}
constexpr barrett_reduce_basic(const barrett_reduce_basic&) = default;
constexpr barrett_reduce_basic(barrett_reduce_basic&&) = default;
barrett_reduce_basic& operator = (const barrett_reduce_basic&) = default;
barrett_reduce_basic& operator = (barrett_reduce_basic&&) = default;
// assume x <= n
constexpr quot_t quot(dividend_t x) const noexcept { return (tmp_t(x) * I) >> k; }
constexpr rem_t rem(dividend_t x) const noexcept { return x - dividend_t(quot(x)) * mod; }
constexpr rem_t operator () (mod_t a, mod_t b) const noexcept { return rem(dividend_t(a) * b); }
constexpr rem_t operator () (mod_t a, mod_t b, mod_t c) const noexcept { return rem(dividend_t(a) * b + c); }
};
using barrett_reduce = barrett_reduce_basic<std::uint32_t, std::uint64_t, std::uint8_t, std::uint64_t, __uint128_t, std::uint64_t>;
inline namespace __fast {
struct reduce { // 只保证 0 < m <= INT_MAX 时正确
typedef std::uint32_t mod_t;
typedef std::uint64_t reg_t;
typedef __uint128_t tmp_t;
mod_t mod;
reg_t mul;
constexpr reduce(mod_t m = 1) : mod(m), mul() {
if (m == 0)throw "mod = 0.";
mul = ((tmp_t(1) << 64) / m) - 1; // 处理 m=1
}
typedef std::uint32_t rem_t;
typedef std::uint64_t dividend_t;
constexpr rem_t rem(dividend_t x) const noexcept {
const rem_t r = x - ((tmp_t(x) * mul + x) >> 64) * mod;
return r >= mod? r - mod : r;
}
constexpr rem_t operator () (mod_t a, mod_t b) const noexcept {
return rem(dividend_t(a) * b);
}
constexpr rem_t operator () (mod_t a, mod_t b, mod_t c) const noexcept {
return rem(dividend_t(a) * b + c);
}
};
struct reduce_n1 { // 只保证 1 < m <= INT_MAX 时正确
typedef std::uint32_t mod_t;
typedef std::uint64_t reg_t;
typedef __uint128_t tmp_t;
mod_t mod;
reg_t mul;
constexpr reduce_n1(mod_t m = 1) : mod(m), mul() {
if (m <= 1)throw "mod <= 1.";
mul = (tmp_t(1) << 64) / m;
}
typedef std::uint32_t rem_t;
typedef std::uint64_t dividend_t;
constexpr rem_t rem(dividend_t x) const noexcept {
const rem_t r = x - (tmp_t(x) * mul >> 64) * mod;
return r >= mod? r - mod : r;
}
constexpr rem_t operator () (mod_t a, mod_t b) const noexcept {
return rem(dividend_t(a) * b);
}
constexpr rem_t operator () (mod_t a, mod_t b, mod_t c) const noexcept {
return rem(dividend_t(a) * b + c);
}
};
} // 实测三者效率相差在波动范围内
// 假定值在模范围内，减少一次取模操作
struct in_mod_range_t { };
constexpr in_mod_range_t in_mod_range {};
template <typename dmodint, typename val_t, typename = void>
struct modval_t;
template <typename dmodint, typename val_t>
struct modval_t<dmodint, val_t, std::enable_if_t<std::is_unsigned<val_t>::value> > {
using mod_t = typename dmodint::mod_t;
static constexpr mod_t modval(val_t x) noexcept {
return dmodint::instacne()(x);
}
};
template <typename dmodint, typename val_t>
struct modval_t<dmodint, val_t, std::enable_if_t<std::is_signed<val_t>::value> > {
using mod_t = typename dmodint::mod_t;
static constexpr mod_t modval(val_t x) noexcept {
x %= dmodint::mod();
if (x < 0)x += dmodint::mod();
return x;
}
};
template <typename reduce>
struct dmodint {
using reduce_t = reduce;
using mod_t = typename reduce::mod_t;
static reduce rdc;
static bool mod_is_prime;
mod_t val;
constexpr dmodint() noexcept : val() { }
constexpr dmodint(const dmodint &) noexcept = default;
constexpr dmodint(dmodint &&) noexcept = default;
constexpr dmodint& operator = (const dmodint &) noexcept = default;
constexpr dmodint& operator = (dmodint &&) noexcept = default;
inline static reduce &instance() noexcept { return rdc; }
inline static mod_t mod() noexcept { return rdc.mod; }
inline static mod_t mul(mod_t a, mod_t b) noexcept { return rdc(a, b); }
inline static mod_t mfma(mod_t a, mod_t b, mod_t c) noexcept { return rdc(a, b, c); }
inline static mod_t rem(typename reduce::dividend_t x) noexcept { return rdc.rem(x); }
template <typename val_t, typename = decltype(modval_t<dmodint, val_t>::modval(std::declval<val_t>()))>
inline dmodint(val_t x) noexcept : val(modval_t<dmodint, val_t>::modval(x)) { }
inline dmodint(in_mod_range_t ir, mod_t x) noexcept : val(x) { }
constexpr mod_t value() const noexcept { return val; }
friend inline dmodint operator + (const dmodint &a, const dmodint &b) noexcept {
mod_t x = a.value() + b.value();
if (x >= mod())x -= mod();
return dmodint(in_mod_range, x);
}
friend inline dmodint operator - (const dmodint &a, const dmodint &b) noexcept {
return dmodint(in_mod_range, a.value() < b.value()? a.value() + mod() - b.value() : a.value() - b.value());
}
friend inline dmodint operator * (const dmodint &a, const dmodint &b) noexcept {
return dmodint(in_mod_range, mul(a.value(), b.value()));
}
friend inline dmodint& operator += (dmodint &a, const dmodint &b) noexcept {
return a = a + b;
}
friend inline dmodint& operator -= (dmodint &a, const dmodint &b) noexcept {
return a = a - b;
}
friend inline dmodint& operator *= (dmodint &a, const dmodint &b) noexcept {
return a = a * b;
}
friend inline dmodint fma(const dmodint &a, const dmodint &b, const dmodint &c) noexcept {
return dmodint(in_mod_range, mfma(a.value(), b.value(), c.value()));
}
friend inline dmodint pow(dmodint a, std::uintmax_t b) noexcept {
dmodint ret(in_mod_range, 1);
for (; b; b >>= 1, a *= a)if (b & 1)ret *= a;
return ret;
}
inline dmodint inv() const noexcept {
if (mod_is_prime){
return pow(*this, mod() - 2);
} else {
// unsupport, UB
}
}
friend inline dmodint operator / (const dmodint &a, const dmodint &b) noexcept {
if (mod_is_prime){
return a * b.inv();
} else {
// unsupport, UB
}
}
friend inline dmodint& operator /= (dmodint &a, const dmodint &b) noexcept {
return a = a / b;
}
};
template <typename reduce>
reduce dmodint<reduce>::rdc = {};
template <typename reduce>
bool dmodint<reduce>::mod_is_prime = false;
}
#include <iostream>
namespace std {
template <typename reduce>
ostream &operator << (ostream &os, const dmodint_nm::dmodint<reduce> &v){
return os << v.value();
}
template <typename reduce>
istream &operator >> (istream &is, dmodint_nm::dmodint<reduce> &v){
uint64_t x;
is >> x;
v = x;
return is;
}
}
#include <bits/stdc++.h>
using namespace std;
int n;
int pl[3010], lp;
void sieve(int n){
static bool pr[3010];
fill_n(pr + 1, n, 1);
for (int i = 2; i <= n; ++i)
if (pr[i]){
pl[++lp] = i;
for (int j = i + i; j <= n; j += i)pr[j] = 0;
}
}
dmodint_nm::barrett_reduce rdc[10010]; int ct;
void sieve2(int n){
static bool pr[100010];
fill_n(pr + 1, n, 1);
for (int i = 2; i <= n; ++i)
if (pr[i]){
rdc[++ct] = {i};
for (int j = i + i; j <= n; j += i)pr[j] = 0;
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
sieve(cbrt(1e10));
sieve2(1e5);
cin >> n;
int rs = 0;
map<long long, pair<int, int> > mp;
while (n--){
long long a;
cin >> a;
for (int x = 1; x <= lp; ++x){
long long t = 1ll * pl[x] * pl[x] * pl[x];
while (a % t == 0)a /= t;
}
if (a == 1){rs = 1;continue;}
long long v = a;
__int128_t o = 1;
for (int x = 1; x <= ct; ++x){
auto qo = rdc[x].quot(v);
if (rdc[x].mod * qo != v)continue;
v = qo; o *= rdc[x].mod;
qo = rdc[x].quot(v);
if (rdc[x].mod * qo != v)o *= rdc[x].mod;
else v = qo;
if (v == 1)break;
}
if (v > 1)o *= v, o *= v;
assert(a != o);
a < o? ++mp[a].first : ++mp[o].second;
}
for (auto [_, a] : mp)rs += max(a.first, a.second);
cout << rs << endl;
return 0;
}
Submission Info
Submission Time
2026-03-24 14:51:50+0900
Task
D - Anticube
User
szt100309
Language
C++23 (GCC 15.2.0)
Score
1100
Code Size
12573 Byte
Status
AC
Exec Time
1307 ms
Memory
10328 KiB
Compile Error
./Main.cpp: In function 'void sieve2(int)':
./Main.cpp:266:26: warning: narrowing conversion of 'i' from 'int' to 'dmodint_nm::barrett_reduce_basic<unsigned int, long unsigned int, unsigned char, long unsigned int, __int128 unsigned, long unsigned int>::mod_t' {aka 'unsigned int'} [-Wnarrowing]
266 | rdc[++ct] = {i};
| ^
./Main.cpp: In function 'int main()':
./Main.cpp:289:33: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'long long int' [-Wsign-compare]
289 | if (rdc[x].mod * qo != v)continue;
| ~~~~~~~~~~~~~~~~^~~~
./Main.cpp:292:33: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'long long int' [-Wsign-compare]
292 | if (rdc[x].mod * qo != v)o *= rdc[x].mod;
| ~~~~~~~~~~~~~~~~^~~~
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1100 / 1100
Status
Set Name
Test Cases
Sample
s1.txt, s2.txt, s3.txt
All
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, s1.txt, s2.txt, s3.txt
Case Name
Status
Exec Time
Memory
01.txt
AC 1109 ms
10228 KiB
02.txt
AC 1088 ms
10328 KiB
03.txt
AC 1062 ms
10180 KiB
04.txt
AC 1097 ms
10288 KiB
05.txt
AC 1090 ms
10160 KiB
06.txt
AC 1086 ms
10172 KiB
07.txt
AC 1088 ms
10224 KiB
08.txt
AC 1077 ms
10300 KiB
09.txt
AC 1079 ms
10160 KiB
10.txt
AC 1093 ms
10320 KiB
11.txt
AC 1307 ms
6096 KiB
12.txt
AC 1303 ms
6000 KiB
13.txt
AC 1141 ms
6000 KiB
14.txt
AC 1138 ms
6156 KiB
15.txt
AC 1141 ms
5936 KiB
16.txt
AC 1147 ms
6004 KiB
17.txt
AC 117 ms
4132 KiB
18.txt
AC 117 ms
4156 KiB
19.txt
AC 117 ms
4184 KiB
20.txt
AC 117 ms
4184 KiB
21.txt
AC 932 ms
7792 KiB
22.txt
AC 922 ms
7716 KiB
23.txt
AC 929 ms
7844 KiB
24.txt
AC 930 ms
7896 KiB
25.txt
AC 929 ms
7876 KiB
26.txt
AC 934 ms
7716 KiB
27.txt
AC 240 ms
9284 KiB
28.txt
AC 105 ms
4080 KiB
29.txt
AC 106 ms
4144 KiB
30.txt
AC 107 ms
4016 KiB
31.txt
AC 107 ms
4144 KiB
32.txt
AC 106 ms
4164 KiB
33.txt
AC 2 ms
4028 KiB
34.txt
AC 113 ms
4132 KiB
35.txt
AC 113 ms
4080 KiB
36.txt
AC 2 ms
4184 KiB
37.txt
AC 1250 ms
6308 KiB
38.txt
AC 1252 ms
6448 KiB
39.txt
AC 1251 ms
6384 KiB
40.txt
AC 1252 ms
6384 KiB
41.txt
AC 2 ms
4012 KiB
42.txt
AC 2 ms
4004 KiB
43.txt
AC 2 ms
4164 KiB
44.txt
AC 2 ms
4016 KiB
45.txt
AC 2 ms
4236 KiB
46.txt
AC 2 ms
4012 KiB
47.txt
AC 2 ms
4016 KiB
48.txt
AC 2 ms
4132 KiB
s1.txt
AC 2 ms
4164 KiB
s2.txt
AC 2 ms
4144 KiB
s3.txt
AC 2 ms
4164 KiB