Skip to content

Instantly share code, notes, and snippets.

@MinecraftFuns

MinecraftFuns/README.md

Last active June 8, 2021 09:18
Show Gist options
  • Save MinecraftFuns/e6138d1ec8a09d6b53fb9c59b0b03442 to your computer and use it in GitHub Desktop.
Save MinecraftFuns/e6138d1ec8a09d6b53fb9c59b0b03442 to your computer and use it in GitHub Desktop.
Download ZIP
CF986 / Codeforces Round 485 (Div. 1)
Raw
a.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int N = 1e5 + 5;
const int K = 100 + 5;
int n, m, k, s;
int a[N];
int dis[N][K];
int head[N], E = 0;
struct Edge
{
int to, next;
} e[N * 2];
inline void addEdge(int u, int v)
{
e[++E] = (Edge){v, head[u]};
head[u] = E;
}
int main()
{
read(n), read(m), read(k), read(s);
for (int i = 1; i <= n; ++i)
{
read(a[i]);
}
for (int i = 1, u, v; i <= m; ++i)
{
read(u), read(v);
addEdge(u, v);
addEdge(v, u);
}
memset(dis, 0x3f, sizeof(dis));
for (int i = 1; i <= k; ++i)
{
queue<int> q;
for (int j = 1; j <= n; ++j)
{
if (a[j] == i)
{
dis[j][i] = 0;
q.emplace(j);
}
}
while (!q.empty())
{
int u = q.front();
q.pop();
for (int j = head[u], v; j; j = e[j].next)
{
v = e[j].to;
if (dis[v][i] > dis[u][i] + 1)
{
dis[v][i] = dis[u][i] + 1;
q.emplace(v);
}
}
}
}
for (int i = 1, sum; i <= n; ++i)
{
sort(dis[i] + 1, dis[i] + k + 1);
sum = 0;
for (int j = 1; j <= s; ++j)
{
sum += dis[i][j];
}
printf("%d ", sum);
}
}
Raw
b.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int N = 1e6 + 5;
int n;
int a[N], b[N];
int main()
{
read(n);
for (int i = 1; i <= n; ++i)
{
read(a[i]);
b[a[i]] = i;
}
int cnt = 0;
for (int i = 1; i <= n; ++i)
{
if (a[i] != i)
{
a[b[i]] = a[i];
b[a[i]] = b[i];
++cnt;
}
}
puts(cnt % 2 == n % 2 ? "Petr" : "Um_nik");
}
Raw
b.pai.cpp
#include <bits/stdc++.h>
using namespace std;
mt19937 mtr(chrono::system_clock::now().time_since_epoch().count());
const unsigned N = 20;
int a[N];
inline void clear()
{
for (int i = 0; i < N; ++i)
{
a[i] = i + 1;
}
}
inline void random_swap()
{
unsigned x = mtr() % N, y = mtr() % N;
swap(a[x], a[y]);
}
int main()
{
while (true)
{
clear();
for (int i = 0; i < N * 3; ++i)
{
random_swap();
}
int cnt = 0;
for (int i = 0; i < N; ++i)
{
if (a[i] % 2 == (i + 1) % 2)
{
++cnt;
}
}
}
}
Raw
bigint.cpp
#include <bits/stdc++.h>
using namespace std;
struct BigInt
{
vector<int> vec;
const int PER = 4;
inline void init(int num)
{
int x = 0, cnt = 0;
while (num != 0)
{
x = x * 10 + num % 10;
++cnt;
if (cnt == PER)
{
vec.emplace_back(x);
x = 0;
cnt = 0;
}
num /= 10;
}
if (cnt != 0)
{
vec.emplace_back(x);
}
}
inline void init(const char *str)
{
int len = strlen(str);
int x = 0, cnt = 0;
for (int i = 0; i < len; ++i)
{
x = x * 10 + str[i] - 'a';
++cnt;
if (cnt == PER)
{
vec.emplace_back(x);
x = 0;
cnt = 0;
}
}
if (cnt != 0)
{
vec.emplace_back(x);
}
}
};
Raw
c.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int N = (2 << 22) + 5;
int a[N], mask;
bool vis[N], mark[N];
int n, m;
int head[N], E = 0;
struct Edge
{
int to, next;
} e[N];
inline void addEdge(int u, int v)
{
e[++E] = (Edge){v, head[u]};
head[u] = E;
}
void dfs(int u)
{
vis[u] = true;
for (int i = head[u], v; i; i = e[i].next)
{
v = e[i].to;
if (!vis[v])
{
dfs(v);
}
}
for (int i = 0, v; i < n; ++i)
{
if (u & (1 << i))
{
v = u ^ (1 << i);
if (!vis[v])
{
dfs(v);
}
}
}
}
int main()
{
read(n), read(m);
mask = (1 << n) - 1;
for (int i = 1; i <= m; ++i)
{
read(a[i]);
addEdge(a[i], a[i] ^ mask);
}
int ans = 0;
for (int i = 1; i <= m; ++i)
{
if (!vis[a[i]])
{
vis[a[i]] = true;
dfs(a[i] ^ mask);
++ans;
}
}
printf("%d\n", ans);
}
Raw
c.ref.cpp
#include <bits/stdc++.h>
using namespace std;
int cnt, n, m, a[5000005], ans, En, head[5000005], vis[5000005];
struct Edge
{
int next, to;
} E[5000005];
void add(int from, int to)
{
En++;
E[En].next = head[from];
E[En].to = to;
head[from] = En; //前向星存图
}
void dfs(int k)
{
vis[k] = 1;
for (int i = head[k]; i; i = E[i].next)
{
int t = E[i].to;
if (vis[t] == 0)
dfs(t); //遍历图
}
for (int i = 1; i <= n; ++i)
if (k & (1 << (i - 1)))
{
int t = k ^ (1 << (i - 1));
if (vis[t] == 0)
dfs(t); //枚举y每一位
}
}
int main()
{
scanf("%d%d", &n, &m);
cnt = (1 << n) - 1; //cnt表示2^(n)-1
for (int i = 1; i <= m; i++)
scanf("%d", &a[i]), add(a[i], a[i] ^ cnt);
for (int i = 1; i <= m; i++) //枚举连通块，累加答案
if (vis[a[i]] == 0)
vis[a[i]] = 1, dfs(a[i] ^ cnt), ans++;
printf("%d\n", ans); //愉快地输出
}
Raw
d.another.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int MAXN = 1 << 19; // FFT array size
const int BASE = 1000; // Must be multiple of 10, use 1000 for FFT stability
const int BASE_DIGITS = log10(BASE);
const int N = 1.5e6 + 5;
const double PI = 3.14159265358979323846;
template <typename Tp>
struct Complex
{
typedef Complex<Tp> Comp;
Tp x, y;
inline Complex(const Tp &_x = 0, const Tp &_y = 0)
{
#if __cplusplus >= 201103L
x = std::move(_x);
y = std::move(_y);
#else
x = _x;
y = _y;
#endif
}
inline const Comp &operator()(const Tp &_x = 0, const Tp &_y = 0)
{
#if __cplusplus >= 201103L
x = std::move(_x);
y = std::move(_y);
#else
x = _x;
y = _y;
#endif
return *this;
}
inline const Comp &operator()(const Comp &rhs)
{
#if __cplusplus >= 201103L
*this = std::move(rhs);
#else
*this = rhs;
#endif
return *this;
}
inline Comp operator+(const Comp &rhs) const
{
return (Comp){x + rhs.x, y + rhs.y};
}
inline const Comp &operator+=(const Comp &rhs)
{
x += rhs.x;
y += rhs.y;
return *this;
}
inline Comp operator-(const Comp &rhs) const
{
return (Comp){x - rhs.x, y - rhs.y};
}
inline const Comp &operator-=(const Comp &rhs)
{
x -= rhs.x;
y -= rhs.y;
return *this;
}
inline Comp operator*(const Comp &rhs) const
{
return (Comp){x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x};
}
inline const Comp &operator*=(const Comp &rhs)
{
*this = (Comp){x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x};
return *this;
}
inline Comp operator/(const Tp &rhs) const
{
return (Comp){x / rhs, y / rhs};
}
inline const Comp &operator/=(const Tp &rhs) const
{
*this = (Comp){x / rhs, y / rhs};
return *this;
}
inline const Tp real() const
{
return x;
}
inline const Tp imag() const
{
return y;
}
inline void real(const Tp &_x)
{
#if __cplusplus >= 201103L
x = std::move(_x);
#else
x = _x;
#endif
}
inline void imag(const Tp &_y)
{
#if __cplusplus >= 201103L
y = std::move(_y);
#else
y = _y;
#endif
}
};
typedef Complex<double> Comp;
// namespace fft
// {
// int LIM, L;
// int R[MAXN];
// inline void init(int n)
// {
// LIM = 1, L = 0;
// while (LIM <= n)
// {
// LIM <<= 1;
// ++L;
// }
// for (int i = 1; i < LIM; ++i)
// {
// R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
// }
// }
// inline void fft(Comp *J, int sign)
// {
// for (int i = 1; i < LIM; i <<= 1)
// {
// Comp T(cos(PI / i), sign * sin(PI / i));
// for (int j = 0; j < LIM; j += (i << 1))
// {
// Comp t(1, 0);
// for (int k = 0; k < i; ++k, t *= T)
// {
// Comp nx = J[j + k], ny = t * J[i + j + k];
// J[j + k] = nx + ny;
// J[i + j + k] = nx - ny;
// }
// }
// }
// if (sign == -1)
// {
// for (int i = 0; i < LIM; ++i)
// {
// J[i] /= LIM;
// }
// }
// }
// } // namespace fft
namespace fft
{
Comp omega[MAXN];
inline void fft(Comp *a, int n)
{
for (int i = 0; i < n; ++i)
{
int j = 0;
int x = i, y = n - 1;
while (y)
{
j = (j << 1) + (x & 1);
x >>= 1;
y >>= 1;
}
if (i < j)
swap(a[i], a[j]);
}
for (int len = 1; len < n; len <<= 1)
{
double angle = 2 * PI / (2 * len);
Comp root(cos(angle), sin(angle));
omega[0] = 1;
for (int i = 1; i < len; ++i)
omega[i] = omega[i - 1] * root;
for (int i = 0; i < n; i += 2 * len)
{
for (int j = 0; j < len; ++j)
{
Comp u = a[i + j];
Comp v = a[i + j + len] * omega[j];
a[i + j] = u + v;
a[i + j + len] = u - v;
}
}
}
}
inline void multiply(Comp *A, Comp *B, ll *C, int n)
{
fft(A, n);
fft(B, n);
for (int i = 0; i < n; ++i)
{
A[i] = A[i] * B[i] / n;
}
fft(A, n);
reverse(A + 1, A + n);
for (int i = 0; i < n; ++i)
C[i] = llround(A[i].x);
}
Comp AA[MAXN], BB[MAXN];
inline void multiply(int *A, int *B, ll *C, int n)
{
for (int i = 0; i < n; ++i)
{
AA[i] = A[i];
BB[i] = B[i];
}
multiply(AA, BB, C, n);
}
}; // namespace fft
struct BigInt
{
vector<int> num;
inline BigInt() {}
inline BigInt(const string &s)
{
for (int i = (int)s.size() - 1; i >= 0; i -= BASE_DIGITS)
{
int x = 0;
for (int j = max(0, i - BASE_DIGITS + 1); j <= i; ++j)
x = x * 10 + s[j] - '0';
num.push_back(x);
}
trim();
}
inline BigInt(ll m) : BigInt(to_string(m)) {}
inline bool operator<(const BigInt &v) const
{
if (num.size() != v.num.size())
return num.size() < v.num.size();
for (int i = (int)num.size() - 1; i >= 0; --i)
if (num[i] != v.num[i])
return num[i] < v.num[i];
return false;
}
inline bool operator>(const BigInt &v) const
{
return v < *this;
}
inline bool operator<=(const BigInt &v) const
{
return !(v < *this);
}
inline bool operator>=(const BigInt &v) const
{
return !(*this < v);
}
inline bool operator==(const BigInt &v) const
{
return num == v.num;
}
inline bool operator!=(const BigInt &v) const
{
return !(*this == v);
}
void trim()
{
while (!num.empty() && !num.back())
num.pop_back();
}
inline BigInt &operator+=(const BigInt &x)
{
int maxs = max(num.size(), x.num.size());
num.resize(maxs);
int carry = 0;
for (int i = 0; i < maxs; ++i)
{
int other = i >= x.num.size() ? 0 : x.num[i];
num[i] += other + carry;
carry = num[i] / BASE;
num[i] %= BASE;
}
if (carry)
num.push_back(carry);
return *this;
}
// assert m * BASE fits in ll
inline BigInt &operator*=(ll m)
{
ll carry = 0;
for (int i = 0; i < num.size(); ++i)
{
ll v = num[i] * m + carry;
carry = v / BASE;
num[i] = v % BASE;
}
while (carry)
{
num.push_back(carry % BASE);
carry /= BASE;
}
trim();
return *this;
}
inline BigInt &operator*=(const BigInt &x)
{
if (num.empty())
return *this;
auto a = num;
auto b = x.num;
int p = 32 - __builtin_clz(a.size() + b.size() - 1);
int n = 1 << p;
a.resize(n);
b.resize(n);
vector<ll> c(n);
fft::multiply(a.data(), b.data(), c.data(), n);
ll carry = 0;
num.resize(n);
for (int i = 0; i < n; ++i)
{
c[i] += carry;
carry = c[i] / BASE;
num[i] = c[i] % BASE;
}
if (carry)
num.push_back(carry);
trim();
return *this;
}
// assert d * BASE fits in ll
inline ll divideAndRemainder(ll d)
{
ll cur = 0;
vector<int> ret;
for (int i = (int)num.size() - 1; i >= 0; --i)
{
cur = cur * BASE + num[i];
ret.push_back(cur / d);
cur %= d;
}
reverse(ret.begin(), ret.end());
num = ret;
trim();
return cur;
}
inline BigInt &operator/=(int v)
{
divideAndRemainder(v);
return *this;
}
inline BigInt operator+(BigInt v) const
{
return BigInt(*this) += v;
}
inline BigInt operator*(ll v) const
{
return BigInt(*this) *= v;
}
inline BigInt operator*(BigInt v) const
{
return BigInt(*this) *= v;
}
inline BigInt operator/(int v) const
{
return BigInt(*this) /= v;
}
};
char str[N];
inline BigInt pow3(int exp)
{
BigInt base = 3;
BigInt res = 1;
while (exp != 0)
{
if (exp & 1)
{
res *= base;
}
base *= base;
exp >>= 1;
}
return res;
}
int main()
{
scanf("%s", str);
if (strcmp(str, "1") == 0)
{
puts("1");
return 0;
}
BigInt N(str);
int len = strlen(str);
int p = ceil((len - 1) / log10l(3));
BigInt x = pow3(p);
while (x < N)
{
++p;
x *= 3;
}
int ans = 3 * p;
for (int num2 = 1; num2 <= 2; ++num2)
{
x *= 2;
while (true)
{
BigInt y = x;
y /= 3;
if (y < N)
{
break;
}
x = y;
--p;
}
ans = std::min(ans, p * 3 + num2 * 2);
}
printf("%d\n", ans);
}
Raw
d.biao.py
def calc(x: int, p: int) -> int:
t, r = divmod(x, p)
res = 1
for _ in range(r):
res *= (t + 1)
for _ in range(r, p):
res *= t
return res
ans_list = []
for N in range(1, 171):
ans = [calc(N, i) for i in range(1, N + 1)]
mx, pos = -1, -1
for i in range(len(ans)):
if ans[i] > mx:
mx = ans[i]
pos = i + 1
print(N)
print(mx, pos)
ans_list.append(mx)
print()
print(*ans_list, sep='\n')
print()
for i in range(len(ans_list) - 1):
print(ans_list[i + 1] / ans_list[i])
Raw
d.cpp
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int MAXN = 1 << 19; // FFT array size
const int BASE = 1000; // Must be multiple of 10, use 1000 for FFT stability
const int BASE_DIGITS = log10(BASE);
const int N = 1.5e6 + 5;
const double PI = 3.14159265358979323846;
struct Complex
{
typedef double valueType;
valueType r, i;
Complex(const valueType &r = 0, const valueType &i = 0) : r(r), i(i) {}
const Complex operator+(const Complex &rhs) const { return (Complex){r + rhs.r, i + rhs.i}; }
const Complex operator-(const Complex &rhs) const { return (Complex){r - rhs.r, i - rhs.i}; }
const Complex operator*(const Complex &rhs) const { return (Complex){r * rhs.r - i * rhs.i, r * rhs.i + i * rhs.r}; }
const Complex operator/(const valueType &rhs) const { return (Complex){r / rhs, i / rhs}; }
};
namespace fft
{
Complex rootpw[MAXN];
inline void fft(Complex *a, int n)
{
for (int i = 0; i < n; ++i)
{
int j = 0;
int x = i, y = n - 1;
while (y)
{
j = (j << 1) + (x & 1);
x >>= 1;
y >>= 1;
}
if (i < j)
swap(a[i], a[j]);
}
for (int len = 1; len < n; len <<= 1)
{
double angle = 2 * PI / (2 * len);
Complex root(cos(angle), sin(angle));
rootpw[0] = 1;
for (int i = 1; i < len; ++i)
rootpw[i] = rootpw[i - 1] * root;
for (int i = 0; i < n; i += 2 * len)
{
for (int j = 0; j < len; ++j)
{
Complex u = a[i + j];
Complex v = a[i + j + len] * rootpw[j];
a[i + j] = u + v;
a[i + j + len] = u - v;
}
}
}
}
inline void multiply(Complex *A, Complex *B, ll *__C, int n)
{
fft(A, n);
fft(B, n);
for (int i = 0; i < n; ++i)
{
A[i] = A[i] * B[i] / n;
}
fft(A, n);
reverse(A + 1, A + n);
for (int i = 0; i < n; ++i)
__C[i] = llround(A[i].r);
}
Complex AA[MAXN], BB[MAXN];
inline void multiply(int *A, int *B, ll *__C, int n)
{
for (int i = 0; i < n; ++i)
{
AA[i] = A[i];
BB[i] = B[i];
}
multiply(AA, BB, __C, n);
}
}; // namespace fft
struct BigInt
{
vector<int> num;
BigInt() {}
BigInt(const string &s)
{
for (int i = (int)s.size() - 1; i >= 0; i -= BASE_DIGITS)
{
int x = 0;
for (int j = max(0, i - BASE_DIGITS + 1); j <= i; ++j)
x = x * 10 + s[j] - '0';
num.push_back(x);
}
trim();
}
BigInt(ll m) : BigInt(to_string(m)) {}
bool operator<(const BigInt &v) const
{
if (num.size() != v.num.size())
return num.size() < v.num.size();
for (int i = (int)num.size() - 1; i >= 0; --i)
if (num[i] != v.num[i])
return num[i] < v.num[i];
return false;
}
bool operator>(const BigInt &v) const
{
return v < *this;
}
bool operator<=(const BigInt &v) const
{
return !(v < *this);
}
bool operator>=(const BigInt &v) const
{
return !(*this < v);
}
bool operator==(const BigInt &v) const
{
return num == v.num;
}
bool operator!=(const BigInt &v) const
{
return !(*this == v);
}
void trim()
{
while (!num.empty() && !num.back())
num.pop_back();
}
BigInt &operator+=(const BigInt &x)
{
int maxs = max(num.size(), x.num.size());
num.resize(maxs);
int carry = 0;
for (int i = 0; i < maxs; ++i)
{
int other = i >= (int)x.num.size() ? 0 : x.num[i];
num[i] += other + carry;
carry = num[i] / BASE;
num[i] %= BASE;
}
if (carry)
num.push_back(carry);
return *this;
}
// assert m * BASE fits in ll
BigInt &operator*=(ll m)
{
ll carry = 0;
for (int i = 0; i < (int)num.size(); ++i)
{
ll v = num[i] * m + carry;
carry = v / BASE;
num[i] = v % BASE;
}
while (carry)
{
num.push_back(carry % BASE);
carry /= BASE;
}
trim();
return *this;
}
BigInt &operator*=(const BigInt &x)
{
if (num.empty())
return *this;
auto a = num;
auto b = x.num;
int p = 32 - __builtin_clz(a.size() + b.size() - 1);
int n = 1 << p;
a.resize(n);
b.resize(n);
vector<ll> c(n);
fft::multiply(a.data(), b.data(), c.data(), n);
ll carry = 0;
num.resize(n);
for (int i = 0; i < n; ++i)
{
c[i] += carry;
carry = c[i] / BASE;
num[i] = c[i] % BASE;
}
if (carry)
num.push_back(carry);
trim();
return *this;
}
// assert d * BASE fits in ll
ll divideAndRemainder(ll d)
{
ll cur = 0;
vector<int> ret;
for (int i = (int)num.size() - 1; i >= 0; --i)
{
cur = cur * BASE + num[i];
ret.push_back(cur / d);
cur %= d;
}
reverse(ret.begin(), ret.end());
num = ret;
trim();
return cur;
}
BigInt &operator/=(int v)
{
divideAndRemainder(v);
return *this;
}
BigInt operator+(BigInt v) const
{
return BigInt(*this) += v;
}
BigInt operator*(ll v) const
{
return BigInt(*this) *= v;
}
BigInt operator*(BigInt v) const
{
return BigInt(*this) *= v;
}
BigInt operator/(int v) const
{
return BigInt(*this) /= v;
}
string str()
{
if (num.empty())
return "0";
string ret = to_string(num.back());
string fmt = "%0" + to_string(BASE_DIGITS) + "d";
for (int i = (int)num.size() - 2; i >= 0; --i)
{
char buf[BASE_DIGITS + 1];
sprintf(buf, fmt.c_str(), num[i]);
ret += buf;
}
return ret;
}
};
char str[N];
BigInt pow3(int exp)
{
if (!exp)
{
return 1;
}
if (exp & 1)
{
return pow3(exp - 1) * 3;
}
BigInt cur = pow3(exp >> 1);
return cur * cur;
}
int main()
{
scanf("%s", str);
if (strcmp(str, "1") == 0)
{
puts("1");
return 0;
}
BigInt N(str);
int len = strlen(str);
int p = ceil((len - 1) / log10l(3));
BigInt x = pow3(p);
while (x < N)
{
++p;
x *= 3;
}
int ans = 3 * p;
for (int num2 = 1; num2 <= 2; ++num2)
{
x *= 2;
while (true)
{
BigInt y = x;
y /= 3;
if (y < N)
{
break;
}
x = y;
--p;
}
ans = std::min(ans, p * 3 + num2 * 2);
}
printf("%d\n", ans);
}
Raw
d.hxb.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
int read()
{
char x = getchar();
int ans = 0, flag = 1;
while (!isdigit(x))
if (x == '-')
flag = -1, x = getchar();
else
x = getchar();
while (isdigit(x))
ans = ans * 10 + x - '0', x = getchar();
return ans * flag;
}
int len;
char s[1500005];
const double log3 = log(10) / log(3), pi = acos(-1);
struct comp
{
double x, y;
comp operator+(comp a) const
{
return comp{x + a.x, y + a.y};
}
comp operator-(comp a) const
{
return comp{x - a.x, y - a.y};
}
comp operator*(comp a) const
{
return comp{x * a.x - y * a.y, x * a.y + y * a.x};
}
} omega[1 << 21], inv[1 << 21];
int rev[1 << 21];
struct poly
{
comp a[1 << 21];
int lim;
void init(int lim)
{
omega[0] = inv[0] = comp{1, 0};
omega[1] = comp{cos(2 * pi / lim), sin(2 * pi / lim)};
for (int i = 1; i < lim; i++)
omega[i] = omega[i - 1] * omega[1];
for (int i = 1; i < lim; i++)
inv[i] = omega[lim - i];
}
void fft(comp *a, comp *omega, int lim)
{
for (int i = 0; i < lim; i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
for (int i = 0; i < lim; i++)
if (i < rev[i])
swap(a[i], a[rev[i]]);
for (int i = 1; i < lim; i <<= 1)
{
int t = lim / (i << 1);
for (int j = 0; j < lim; j += (i << 1))
{
for (int k = 0; k < i; k++)
{
comp tmp = omega[t * k] * a[i + j + k];
a[i + j + k] = a[k + j] - tmp;
a[k + j] = a[k + j] + tmp;
}
}
}
}
};
void mul(poly &A, poly B)
{
int lim = 1;
while (lim < A.lim + B.lim - 1)
lim <<= 1;
A.init(lim);
for (int i = 0; i < lim; i++)
A.a[i].y = B.a[i].y = 0;
for (int i = A.lim; i < lim; i++)
A.a[i].x = 0;
for (int i = B.lim; i < lim; i++)
B.a[i].x = 0;
A.fft(A.a, omega, lim);
B.fft(B.a, omega, lim);
for (int i = 0; i < lim; i++)
A.a[i] = A.a[i] * B.a[i];
A.fft(A.a, inv, lim);
for (int i = 0; i < lim; i++)
A.a[i].x = int(A.a[i].x / lim + 0.5);
for (int i = 0; i < lim; i++)
{
A.a[i + 1].x += int(A.a[i].x) / 100;
A.a[i].x = int(A.a[i].x) % 100;
if (i + 1 == lim && A.a[i + 1].x > 0)
lim++;
}
lim++;
while (!A.a[lim - 1].x)
lim--;
A.lim = lim;
}
poly ksm(int p)
{
poly ans, k;
ans.a[0].x = 1;
k.a[0].x = 3;
ans.lim = k.lim = 1;
while (p)
{
if (p & 1)
mul(ans, k);
int lim = 1;
while (lim < k.lim + k.lim - 1)
lim <<= 1;
k.init(lim);
for (int i = 0; i < lim; i++)
k.a[i].y = 0;
for (int i = k.lim; i < lim; i++)
k.a[i].x = 0;
k.fft(k.a, omega, lim);
for (int i = 0; i < lim; i++)
k.a[i] = k.a[i] * k.a[i];
k.fft(k.a, inv, lim);
for (int i = 0; i < lim; i++)
k.a[i].x = int(k.a[i].x / lim + 0.5);
for (int i = 0; i < lim; i++)
{
k.a[i + 1].x += int(k.a[i].x) / 100;
k.a[i].x = int(k.a[i].x) % 100;
if (i + 1 == lim && k.a[i + 1].x > 0)
lim++;
}
lim++;
while (!k.a[lim - 1].x)
lim--;
k.lim = lim;
p >>= 1;
}
return ans;
}
int pow3[] = {1, 3, 9, 27, 81, 243, 729, 6561};
bool mul(poly A, int k, int t)
{
int tmp = 0;
char c[2000005];
if (k <= 2)
{
c[0] = k + '0';
int Len = strlen(c);
if (Len < len)
return 0;
if (Len > len)
return 1;
for (int i = 0; i < len; i++)
if (c[i] < s[i])
return 0;
else
{
cout << k;
return 1;
}
cout << k;
return 1;
}
else if (k % 3 == 0)
tmp = pow3[k / 3 - t];
else if (k % 3 == 1)
tmp = pow3[k / 3 - t - 1] * 4;
else
tmp = pow3[k / 3 - t] * 2;
for (int i = 0; i < A.lim; i++)
A.a[i].x *= tmp;
for (int i = 0; i < A.lim; i++)
{
A.a[i + 1].x += (int)A.a[i].x / 100;
A.a[i].x = (int)A.a[i].x % 100;
if (i + 1 == A.lim && A.a[i + 1].x > 0)
A.lim++;
}
int Len = 0;
for (int i = 0; i < A.lim; i++)
c[Len++] = (int)A.a[i].x % 10 + '0', c[Len++] = (int)A.a[i].x / 10 + '0';
while ('0' == c[Len - 1])
Len--;
if (Len < len)
return 0;
if (Len > len)
{
cout << k;
return 1;
}
reverse(c, c + Len);
for (int i = 0; i < len; i++)
if (s[i] > c[i])
return 0;
else if (s[i] < c[i])
{
cout << k;
return 1;
}
cout << k;
return 1;
}
signed main()
{
cin >> (s);
len = strlen(s);
int tot = 3 * (1.0 * (len - 1) * log(10) / log(3) + log(s[0] - '0') / log(3));
int t = max(0, tot / 3 - 1);
poly A = ksm(t);
for (int i = tot;; i++)
{
if (mul(A, i, t))
return 0;
}
return 0;
}
Raw
d.pai.cpp
#include <bits/stdc++.h>
using namespace std;
inline int calc(int x, int p)
{
int t = x / p, r = x % p;
int res = 1;
for (int i = 0; i < r; ++i)
{
res *= (t + 1);
if (res < 0)
{
exit(-1);
}
}
for (int i = r; i < p; ++i)
{
res *= t;
if (res < 0)
{
exit(-1);
}
}
return res;
}
const int N = 30;
int ans[N];
int main()
{
for (int i = 1; i <= N; ++i)
{
ans[i] = calc(N, i);
}
int *p = max_element(ans + 1, ans + N + 1);
cout << p - ans << " " << *p << endl;
for (int i = 1; i <= N; ++i)
{
cout << ans[i] << " ";
}
}
Raw
d.pai.py
def calc(x: int, p: int) -> int:
t, r = divmod(x, p)
res = 1
for _ in range(r):
res *= (t + 1)
for _ in range(r, p):
res *= t
return res
N = 190
ans = [calc(N, i) for i in range(1, N + 1)]
mx, pos = -1, -1
for i in range(len(ans)):
if ans[i] > mx:
mx = ans[i]
pos = i + 1
print(mx, pos)
print(*ans)
Raw
d.py
n = int(input())
Raw
d.ref.cpp
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include "bits/stdc++.h"
#define mem(x) memset((x), 0, sizeof((x)))
#define il __attribute__((always_inline))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#if __cplusplus > 201403L
#define R
#else
#define R register
#endif
#if __cplusplus >= 201103L
#define C constexpr
#define H_V
#else
#define C const
#endif
#define for_each(con, it) for (__typeof(con.begin()) it = con.begin(); it != con.end(); it++)
namespace _c
{
C double pi = 3.141592653589793;
namespace min
{
C int i8 = -128;
C int i16 = -32768;
C int i = -2147483647 - 1;
C ll l = -9223372036854775807LL - 1;
} // namespace min
namespace max
{
C int i8 = 127;
C int i16 = 32767;
C int i = 2147483647;
C ll l = 9223372036854775807LL;
} // namespace max
} // namespace _c
namespace _f
{
template <typename Tp>
inline Tp gcd(Tp x, Tp y)
{
while (y != 0)
{
Tp t = x % y;
x = y;
y = t;
}
return x;
}
template <typename Tp>
inline Tp abs(const Tp &a)
{
return a > 0 ? a : -a;
}
template <typename Bp, typename Ep>
inline Bp pow(Bp a, Ep b)
{
R Bp res = 1;
while (b > 0)
{
if (b & 1)
{
res *= a;
}
a *= a;
b >>= 1;
}
return res;
}
template <typename Bp, typename Ep, typename Mp>
inline Mp pow(Bp a, Ep b, const Mp &m)
{
a %= m;
R Mp res = 1;
while (b > 0)
{
if (b & 1)
{
res = ((ll)res * a) % m;
}
a = ((ll)a * a) % m;
b >>= 1;
}
return res % m;
}
} // namespace _f
namespace io
{
template <typename Tp>
inline void read(Tp &x)
{
static bool neg;
static char c;
x = 0, neg = 0, c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = 1;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
template <typename Tp>
inline Tp read()
{
R Tp res;
read(res);
return res;
}
template <typename Tp>
inline void readln(const Tp first, const Tp last)
{
for (R Tp it = first; it != last; it++)
{
read(*it);
}
}
template <typename Tp>
inline void _write(Tp x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
{
_write(x / 10);
}
putchar(x % 10 + '0');
}
template <typename Tp>
inline void write(const Tp &x, const char &sep = ' ')
{
_write(x);
putchar(sep);
}
template <typename Tp>
inline void writeln(const Tp &x)
{
write(x, '\n');
}
template <typename Tp>
inline void writeln(const Tp first, const Tp last, const char &sep = ' ', const char &ends = '\n')
{
for (R Tp it = first; it != last; it++)
{
write(*it, sep);
}
putchar(ends);
}
#ifdef H_V
template <typename Tp, typename... Args>
inline void read(Tp &x, Args &... args)
{
read(x);
read(args...);
}
#endif
} // namespace io
#define db(x) std::cerr << #x << ": " << x << std::endl
#define db2(x, y) std::cerr << #x << ": " << x << "; " << #y << ": " << y << std::endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dba(a, n) \
cerr << #a << "="; \
for (int i = 0; i < (n); ++i) \
cerr << a[i] << ", "; \
cerr << endl
#ifdef H_V
#define dbv(v) \
cerr << #v << "="; \
for (auto x : v) \
cerr << x << ", "; \
cerr << endl
#endif
C int MAXN = 1 << 19; // FFT array size
C int BASE = 1000; // Must be multiple of 10, use 1000 for FFT stability
const int BASE_DIGITS = log10(BASE);
const double PI = acos(-1);
typedef double __TYPE__;
struct __COMPLEX__
{
__TYPE__ r, i;
__COMPLEX__(const __TYPE__ &r = 0, const __TYPE__ &i = 0) : r(r), i(i) {}
const __COMPLEX__ operator+(const __COMPLEX__ &rhs) const { return (__COMPLEX__){r + rhs.r, i + rhs.i}; }
const __COMPLEX__ operator-(const __COMPLEX__ &rhs) const { return (__COMPLEX__){r - rhs.r, i - rhs.i}; }
const __COMPLEX__ operator*(const __COMPLEX__ &rhs) const { return (__COMPLEX__){r * rhs.r - i * rhs.i, r * rhs.i + i * rhs.r}; }
const __COMPLEX__ operator/(const __TYPE__ &rhs) const { return (__COMPLEX__){r / rhs, i / rhs}; }
};
namespace fft
{
__COMPLEX__ rootpw[MAXN];
inline void fft(__COMPLEX__ *a, int n)
{
for (int i = 0; i < n; ++i)
{
int j = 0;
int x = i, y = n - 1;
while (y)
{
j = (j << 1) + (x & 1);
x >>= 1;
y >>= 1;
}
if (i < j)
swap(a[i], a[j]);
}
for (int len = 1; len < n; len <<= 1)
{
__TYPE__ angle = 2 * PI / (2 * len);
__COMPLEX__ root(cos(angle), sin(angle));
rootpw[0] = 1;
for (int i = 1; i < len; ++i)
rootpw[i] = rootpw[i - 1] * root;
for (int i = 0; i < n; i += 2 * len)
{
for (int j = 0; j < len; ++j)
{
__COMPLEX__ u = a[i + j];
__COMPLEX__ v = a[i + j + len] * rootpw[j];
a[i + j] = u + v;
a[i + j + len] = u - v;
}
}
}
}
inline void multiply(__COMPLEX__ *A, __COMPLEX__ *B, ll *__C, int n)
{
fft(A, n);
fft(B, n);
for (int i = 0; i < n; ++i)
{
A[i] = A[i] * B[i] / n;
}
fft(A, n);
reverse(A + 1, A + n);
for (int i = 0; i < n; ++i)
__C[i] = llround(A[i].r);
}
__COMPLEX__ AA[MAXN], BB[MAXN];
inline void multiply(int *A, int *B, ll *__C, int n)
{
for (int i = 0; i < n; ++i)
{
AA[i] = A[i];
BB[i] = B[i];
}
multiply(AA, BB, __C, n);
}
}; // namespace fft
struct BigInt
{
vector<int> num;
BigInt() {}
BigInt(const string &s)
{
for (int i = (int)s.size() - 1; i >= 0; i -= BASE_DIGITS)
{
int x = 0;
for (int j = max(0, i - BASE_DIGITS + 1); j <= i; ++j)
x = x * 10 + s[j] - '0';
num.push_back(x);
}
trim();
}
BigInt(ll m) : BigInt(to_string(m)) {}
bool operator<(const BigInt &v) const
{
if (num.size() != v.num.size())
return num.size() < v.num.size();
for (int i = (int)num.size() - 1; i >= 0; --i)
if (num[i] != v.num[i])
return num[i] < v.num[i];
return false;
}
bool operator>(const BigInt &v) const
{
return v < *this;
}
bool operator<=(const BigInt &v) const
{
return !(v < *this);
}
bool operator>=(const BigInt &v) const
{
return !(*this < v);
}
bool operator==(const BigInt &v) const
{
return num == v.num;
}
bool operator!=(const BigInt &v) const
{
return !(*this == v);
}
void trim()
{
while (!num.empty() && !num.back())
num.pop_back();
}
BigInt &operator+=(const BigInt &x)
{
int maxs = max(num.size(), x.num.size());
num.resize(maxs);
int carry = 0;
for (int i = 0; i < maxs; ++i)
{
int other = i >= x.num.size() ? 0 : x.num[i];
num[i] += other + carry;
carry = num[i] / BASE;
num[i] %= BASE;
}
if (carry)
num.push_back(carry);
return *this;
}
// assert m * BASE fits in ll
BigInt &operator*=(ll m)
{
ll carry = 0;
for (int i = 0; i < num.size(); ++i)
{
ll v = num[i] * m + carry;
carry = v / BASE;
num[i] = v % BASE;
}
while (carry)
{
num.push_back(carry % BASE);
carry /= BASE;
}
trim();
return *this;
}
BigInt &operator*=(const BigInt &x)
{
if (num.empty())
return *this;
auto a = num;
auto b = x.num;
int p = 32 - __builtin_clz(a.size() + b.size() - 1);
int n = 1 << p;
a.resize(n);
b.resize(n);
vector<ll> c(n);
fft::multiply(a.data(), b.data(), c.data(), n);
ll carry = 0;
num.resize(n);
for (int i = 0; i < n; ++i)
{
c[i] += carry;
carry = c[i] / BASE;
num[i] = c[i] % BASE;
}
if (carry)
num.push_back(carry);
trim();
return *this;
}
// assert d * BASE fits in ll
ll divideAndRemainder(ll d)
{
ll cur = 0;
vector<int> ret;
for (int i = (int)num.size() - 1; i >= 0; --i)
{
cur = cur * BASE + num[i];
ret.push_back(cur / d);
cur %= d;
}
reverse(ret.begin(), ret.end());
num = ret;
trim();
return cur;
}
BigInt &operator/=(int v)
{
divideAndRemainder(v);
return *this;
}
BigInt operator+(BigInt v) const
{
return BigInt(*this) += v;
}
BigInt operator*(ll v) const
{
return BigInt(*this) *= v;
}
BigInt operator*(BigInt v) const
{
return BigInt(*this) *= v;
}
BigInt operator/(int v) const
{
return BigInt(*this) /= v;
}
string str()
{
if (num.empty())
return "0";
string ret = to_string(num.back());
string fmt = "%0" + to_string(BASE_DIGITS) + "d";
for (int i = (int)num.size() - 2; i >= 0; --i)
{
char buf[BASE_DIGITS + 1];
sprintf(buf, fmt.c_str(), num[i]);
ret += buf;
}
return ret;
}
};
char S[1500005];
BigInt getp3(int p)
{
if (!p)
{
return 1;
}
if (p & 1)
{
return getp3(p - 1) * 3;
}
R auto x = getp3(p >> 1);
return x * x;
}
int main()
{
scanf("%s", S);
if (strcmp(S, "1") == 0)
{
puts("1");
return 0;
}
BigInt N(S);
R int ans = INT_MAX;
R int len = strlen(S);
R int p = ceil((len - 1) / log10l(3));
BigInt x = getp3(p);
while (x < N)
{
++p;
x *= 3;
}
ans = 3 * p;
for (R int num2 = 1; num2 <= 2; ++num2)
{
x *= 2;
for (;;)
{
R auto y = x;
y /= 3;
if (y < N)
break;
x = y;
--p;
}
ans = std::min(ans, p * 3 + num2 * 2);
}
io::writeln(ans);
}
Raw
e.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int N = 1e5 + 5;
const int BZ = 17;
const int MOD = 1e9 + 7;
inline int power(int base, int exp)
{
int res = 1;
while (exp != 0)
{
if (exp & 1)
{
res = (ll)res * base % MOD;
}
base = (ll)base * base % MOD;
exp >>= 1;
}
return res;
}
int n, q;
const int P = 1e7 + 5;
const int PMX = 7e5 + 5;
int prime[PMX], primeCnt = 0;
bool notPrime[P];
inline void sieve()
{
notPrime[1] = true;
for (int i = 2; i < P; ++i)
{
if (!notPrime[i])
{
prime[primeCnt++] = i;
}
for (int j = 0, p; j < primeCnt && (p = prime[j]) && i * p < P; ++j)
{
notPrime[i * p] = true;
if (i % p == 0)
{
break;
}
}
}
}
int head[N], E = 0;
struct Edge
{
int to, next;
} e[N * 2];
int val[N];
inline void addEdge(int u, int v)
{
e[++E] = (Edge){v, head[u]};
head[u] = E;
}
int dep[N], fa[N][BZ];
void dfs(int u, int far)
{
dep[u] = dep[far] + 1;
fa[u][0] = far;
for (int i = 1; i < BZ; ++i)
{
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for (int i = head[u], v; i; i = e[i].next)
{
v = e[i].to;
if (v != far)
{
dfs(v, u);
}
}
}
inline int lca(int u, int v)
{
if (dep[u] < dep[v])
{
swap(u, v);
}
for (int i = BZ - 1; i >= 0; --i)
{
if (dep[fa[u][i]] >= dep[v])
{
u = fa[u][i];
}
}
if (u == v)
{
return u;
}
for (int i = BZ - 1; i >= 0; --i)
{
if (fa[u][i] != fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
namespace Sol
{
int ans[N], W[N];
vector<int> query[N];
vector<int> now[PMX];
inline void add(int val, int type)
{
int cnt;
for (int i = 0, p; i < primeCnt; ++i)
{
p = prime[i];
if (p * p > val)
{
break;
}
if (val % p == 0)
{
cnt = 0;
do
{
val /= p;
++cnt;
} while (val % p == 0);
now[i][cnt] += type;
}
}
if (val != 1)
{
int pos = lower_bound(prime, prime + primeCnt, val) - prime;
now[pos][1] += type;
}
}
inline int calc(int val)
{
int res = 1, cnt, exp;
for (int pi = 0, p; pi < primeCnt; ++pi)
{
p = prime[pi];
if (p * p > val)
{
break;
}
if (val % p == 0)
{
cnt = 0;
do
{
val /= p;
++cnt;
} while (val % p == 0);
exp = 0;
for (int i = 1; i <= cnt; ++i)
{
exp += now[pi][i] * i;
}
for (int i = cnt + 1; i < (int)now[pi].size(); ++i)
{
exp += now[pi][i] * cnt;
}
res = (ll)res * power(p, exp) % MOD;
}
}
if (val != 0)
{
exp = 0;
int pos = lower_bound(prime, prime + primeCnt, val) - prime;
for (int i = 1; i < (int)now[pos].size(); ++i)
{
exp += now[pos][i];
}
res = (ll)res * power(val, exp) % MOD;
}
return res;
}
void dfs(int u, int fa)
{
add(val[u], 1);
int r;
for (auto &q : query[u])
{
if (q > 0)
{
r = calc(W[q]);
ans[q] = (ll)ans[q] * r % MOD;
}
else
{
q = -q; // 反正就用一次，改了也没关系
r = calc(W[q]);
ans[q] = (ll)ans[q] * power((ll)r * r % MOD, MOD - 2) % MOD * gcd(W[q], val[u]) % MOD;
}
}
for (int i = head[u], v; i; i = e[i].next)
{
v = e[i].to;
if (v != fa)
{
dfs(v, u);
}
}
add(val[u], -1);
}
} // namespace Sol
int main()
{
sieve();
read(n);
for (int i = 1, u, v; i < n; ++i)
{
read(u), read(v);
addEdge(u, v);
addEdge(v, u);
}
for (int i = 1, cnt; i <= n; ++i)
{
read(val[i]);
}
dfs(1, 0);
read(q);
fill(Sol::ans + 1, Sol::ans + q + 1, 1);
for (int i = 1, u, v, w, l; i <= q; ++i)
{
read(u), read(v), read(w);
l = lca(u, v);
Sol::W[i] = w;
Sol::query[u].emplace_back(i);
Sol::query[v].emplace_back(i);
Sol::query[l].emplace_back(-i);
}
for (int i = 0, p; i < primeCnt; ++i)
{
p = prime[i];
Sol::now[i].resize(ceil(log(1e7) / log(p)) + 1, 0);
}
Sol::dfs(1, 0);
for (int i = 1; i <= q; ++i)
{
printf("%d\n", Sol::ans[i]);
}
}
Raw
e.debug.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
const int N = 1e5 + 5;
const int BZ = 17;
const int MOD = 1e9 + 7;
inline int power(int base, int exp)
{
int res = 1;
while (exp != 0)
{
if (exp & 1)
{
res = (ll)res * base % MOD;
}
base = (ll)base * base % MOD;
exp >>= 1;
}
return res;
}
int n, q;
const int P = 1e7 + 5;
vector<int> primes;
bool notPrime[P];
inline void init()
{
primes.reserve(7e5);
notPrime[1] = true;
for (int i = 2; i < N; ++i)
{
if (!notPrime[i])
{
primes.emplace_back(i);
}
for (const auto &p : primes)
{
if (i * p >= N)
{
break;
}
notPrime[i * p] = true;
if (i % p == 0)
{
break;
}
}
}
}
const int Q = 113027;
int main()
{
for (int i = 1; i <= Q; ++i)
{
if (Q % i == 0)
{
watch(i);
}
}
}
Raw
e.hxb.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define int long long
int read()
{
char x = getchar();
int ans = 0, flag = 1;
while (!isdigit(x))
if (x == '-')
flag = -1, x = getchar();
else
x = getchar();
while (isdigit(x))
ans = ans * 10 + x - '0', x = getchar();
return ans * flag;
}
int n, m;
const int mod = 1e9 + 7;
bool is_prime[10000005];
int prime[700005], cnt, pnt[200005], nxt[200005], head[100005], E, dep[100005];
int bz[100005][20], ans[100005], a[100005];
void check()
{
for (int i = 2; i <= 10000000; i++)
{
if (!is_prime[i])
prime[++cnt] = i;
for (int j = 1; j <= cnt; j++)
{
if (1ll * i * prime[j] >= 10000000)
break;
is_prime[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
}
int mo(int x)
{
if (x < 0)
x += mod;
if (x >= mod)
x -= mod;
return x;
}
int ksm(int a, int p)
{
int ans = 1;
while (p)
{
if (p & 1)
ans = 1ll * ans * a % mod;
a = 1ll * a * a % mod;
p >>= 1;
}
return ans;
}
struct node
{
int id, opt, val, cnt;
};
vector<node> Q[100005];
vector<pair<int, int>> V[100005];
int gcd(int x, int y)
{
if (!x)
return y;
return gcd(y % x, x);
}
void add_edge(int u, int v)
{
pnt[E] = v;
nxt[E] = head[u];
head[u] = E++;
}
vector<int> sum1[10000005], sum2[10000005];
void dfs(int u, int pre)
{
dep[u] = dep[pre] + 1;
bz[u][0] = pre;
for (int i = 1; i <= 16; i++)
bz[u][i] = bz[bz[u][i - 1]][i - 1];
for (int i = head[u]; i != -1; i = nxt[i])
{
int v = pnt[i];
if (v == pre)
continue;
dfs(v, u);
}
}
int lca(int x, int y)
{
if (dep[x] < dep[y])
swap(x, y);
for (int i = 16; i >= 0; i--)
if (dep[bz[x][i]] >= dep[y])
x = bz[x][i];
if (x == y)
return x;
for (int i = 16; i >= 0; i--)
if (bz[x][i] != bz[y][i])
x = bz[x][i], y = bz[y][i];
return bz[x][0];
}
void dfs1(int u, int pre)
{
for (int i = 0; i < V[u].size(); i++)
{
int x = V[u][i].first, y = V[u][i].second;
for (int j = y; j < sum1[x].size(); j++)
sum1[x][j]++, sum2[x][j] = mo(sum2[x][j] * ksm(x, y) % mod);
}
for (int i = 0; i < Q[u].size(); i++)
{
int id = Q[u][i].id, opt = Q[u][i].opt, cnt = Q[u][i].cnt, val = Q[u][i].val;
int tmp = sum2[val][cnt];
int tmpp = sum1[val][sum1[val].size() - 1] - sum1[val][cnt];
tmp = mo(tmp % mod * ksm(val, tmpp * cnt) % mod);
if (opt == -1)
tmp = ksm(tmp, mod - 2), tmp = tmp * tmp % mod;
ans[id] = 1ll * ans[id] * tmp % mod;
ans[id] = mo(ans[id]);
}
for (int i = head[u]; i != -1; i = nxt[i])
{
int v = pnt[i];
if (v == pre)
continue;
dfs1(v, u);
}
for (int i = 0; i < V[u].size(); i++)
{
int x = V[u][i].first, y = V[u][i].second;
for (int j = y; j < sum1[x].size(); j++)
sum1[x][j]--, sum2[x][j] = mo(sum2[x][j] * ksm(ksm(x, y), mod - 2) % mod);
}
}
signed main()
{
memset(head, -1, sizeof(head));
check();
n = read();
for (int i = 1; i < n; i++)
{
int u = read(), v = read();
add_edge(u, v);
add_edge(v, u);
}
for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i <= n; i++)
{
int tmp = a[i];
for (int j = 1; j <= cnt && 1ll * prime[j] * prime[j] <= a[i]; j++)
{
if (a[i] % prime[j] == 0)
{
int cnt = 0;
while (a[i] % prime[j] == 0)
cnt++, a[i] /= prime[j];
V[i].push_back(make_pair(prime[j], cnt));
}
}
if (a[i] != 1)
V[i].push_back(make_pair(a[i], 1));
a[i] = tmp;
}
dfs(1, 0);
m = read();
for (int i = 1; i <= m; i++)
{
int x = read(), y = read(), w = read(), tmp = w;
int LCA = lca(x, y);
for (int j = 1; j <= cnt && 1ll * prime[j] * prime[j] <= w; j++)
{
if (w % prime[j] == 0)
{
int cnt = 0;
while (w % prime[j] == 0)
cnt++, w /= prime[j];
Q[x].push_back(node{i, 1, prime[j], cnt});
Q[y].push_back(node{i, 1, prime[j], cnt});
Q[LCA].push_back(node{i, -1, prime[j], cnt});
}
}
if (w != 1)
{
Q[x].push_back(node{i, 1, w, 1});
Q[y].push_back(node{i, 1, w, 1});
Q[LCA].push_back(node{i, -1, w, 1});
}
ans[i] = gcd(a[LCA], tmp);
}
for (int i = 1; i <= cnt; i++)
{
ll tmp = 1;
while (tmp <= 10000000)
{
sum1[prime[i]].push_back(0);
sum2[prime[i]].push_back(1);
tmp *= prime[i];
}
}
dfs1(1, 0);
for (int i = 1; i <= m; i++)
cout << ans[i] << '\n';
return 0;
}
Raw
e.ref.cpp
#include <bits/stdc++.h>
#define MD 16
#define MN 100000
#define mod 1000000007
#define MX 10000000
using namespace std;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
bool b[MX + 5];
vector<pair<int, pair<int, int>>> v[MN + 5];
int n, m, last[MX + 5], s[MX / 5], num, a[MN + 5], head[MN + 5], cnt;
int fa[MD + 1][MN + 5], dep[MN + 5], f[MX + 5], Ans[MN + 5];
struct edge
{
int to, next;
} e[MN * 2 + 5];
struct eve
{
int a, b, c;
} q[MN * 30 + 5];
inline int pow(int x, int k)
{
int res = 1;
for (; k; k >>= 1, x = 1LL * x * x % mod)
if (k & 1)
res = 1LL * res * x % mod;
return res;
}
inline void ins(int f, int t)
{
e[++cnt] = (edge){t, head[f]};
head[f] = cnt;
e[++cnt] = (edge){f, head[t]};
head[t] = cnt;
}
void dfs(int x, int f)
{
fa[0][x] = f;
for (int i = head[x]; i; i = e[i].next)
if (e[i].to != f)
dep[e[i].to] = dep[x] + 1, dfs(e[i].to, x);
}
inline int lca(int x, int y)
{
if (dep[x] < dep[y])
swap(x, y);
for (int k = dep[x] - dep[y], j = 0; k; k >>= 1, ++j)
if (k & 1)
x = fa[j][x];
if (x == y)
return x;
for (int i = MD; ~i; --i)
if (fa[i][x] != fa[i][y])
x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
void Solve(int x, int fa)
{
for (int t = a[x]; t > 1;)
for (int p = last[t], y = 1; t % p == 0; t /= p)
++f[y *= p];
for (int j = 0; j < v[x].size(); ++j)
q[v[x][j].first].c += v[x][j].second.second * f[v[x][j].second.first];
for (int i = head[x]; i; i = e[i].next)
if (e[i].to != fa)
Solve(e[i].to, x);
for (int t = a[x]; t > 1;)
for (int p = last[t], y = 1; t % p == 0; t /= p)
--f[y *= p];
}
int main()
{
n = read();
for (int i = 1; i < n; ++i)
ins(read(), read());
for (int i = 1; i <= n; ++i)
a[i] = read();
for (int j = 2; j <= MX; ++j)
{
if (!b[j])
s[++num] = j, last[j] = j;
for (int i = 1; s[i] * j <= MX; ++i)
{
b[s[i] * j] = 1;
last[s[i] * j] = s[i];
if (j % s[i] == 0)
break;
}
}
dfs(1, 0);
cnt = 0;
for (int i = 1; i <= MD; ++i)
for (int j = 1; j <= n; ++j)
fa[i][j] = fa[i - 1][fa[i - 1][j]];
m = read();
for (int i = 1; i <= m; ++i)
{
int a = read(), b = read(), c = lca(a, b), x = read();
Ans[i] = 1;
while (x > 1)
{
int p = last[x], y = 1;
q[++cnt] = (eve){i, p, 0};
while (x % p == 0)
{
x /= p;
y *= p;
v[a].push_back(make_pair(cnt, make_pair(y, 1)));
v[b].push_back(make_pair(cnt, make_pair(y, 1)));
v[c].push_back(make_pair(cnt, make_pair(y, -1)));
if (c > 1)
v[fa[0][c]].push_back(make_pair(cnt, make_pair(y, -1)));
}
}
}
Solve(1, 0);
for (int i = 1; i <= cnt; ++i)
Ans[q[i].a] = 1LL * Ans[q[i].a] * pow(q[i].b, q[i].c) % mod;
for (int i = 1; i <= m; ++i)
printf("%d\n", Ans[i]);
return 0;
}
Raw
e.refer.cpp
//@winlere
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define inv(x) (ksm((x) % mod, mod - 2))
using namespace std;
typedef long long ll;
inline int qr()
{
register int ret = 0, f = 0;
register char c = getchar();
while (c < 48 || c > 57)
f |= c == 45, c = getchar();
while (c >= 48 && c <= 57)
ret = ret * 10 + c - 48, c = getchar();
return f ? -ret : ret;
}
const int mod = 1e9 + 7;
int n, m;
inline int ksm(const int &ba, const int &p)
{
int ret = 1;
for (int t = p, b = ba % mod; t; t >>= 1, b = 1ll * b * b % mod)
if (t & 1)
ret = 1ll * ret * b % mod;
return ret;
}
vector<vector<int>> s;
namespace PRE
{
const int maxn = 1e7 + 5;
int rank[maxn], usd[maxn], arc[maxn], Min[maxn];
vector<int> pr;
inline void pre(const int &n)
{
usd[1] = 1;
Min[1] = 10;
for (int t = 2; t <= n; ++t)
{
if (!usd[t])
Min[t] = t, pr.push_back(t), rank[t] = pr.size(), arc[rank[t]] = t;
for (auto f : pr)
{
if (1ll * f * t > n)
break;
usd[f * t] = 1;
Min[f * t] = f;
if (t % f == 0)
break;
}
}
s.resize(pr.size() + 1);
}
} // namespace PRE
namespace TREE
{
const int maxn = 1e5 + 5;
int d[maxn];
vector<int> e[maxn];
vector<int> q[maxn];
int W[maxn], ans[maxn], w[maxn];
inline void add(const int &fr, const int &to)
{
e[fr].push_back(to);
e[to].push_back(fr);
}
int son[maxn], top[maxn], r[maxn], siz[maxn];
void pre(const int &now, const int &last)
{
siz[now] = 1;
r[now] = last;
d[now] = d[last] + 1;
for (auto t : e[now])
if (t ^ last)
{
pre(t, now);
siz[now] += siz[t];
if (siz[now] > siz[son[now]])
son[now] = t;
}
}
void qaq(const int &now, const int &last)
{
top[now] = last;
if (son[now])
qaq(son[now], last);
for (auto t : e[now])
if ((t ^ r[now]) && (t ^ son[now]))
qaq(t, t);
}
inline void init(const int &n)
{
pre(1, 0);
qaq(1, 0);
}
inline int lca(int u, int v)
{
if (d[u] < d[v])
swap(u, v);
while (top[u] ^ top[v])
{
if (d[top[u]] < d[top[v]])
swap(u, v);
u = r[top[u]];
}
return d[u] < d[v] ? u : v;
}
inline void addq(const int &x, const int &y, const int &id, const int &w)
{
ans[id] = 1;
q[x].push_back(id);
q[y].push_back(id);
q[lca(x, y)].push_back(-id);
W[id] = w;
}
} // namespace TREE
namespace sol
{
const int maxn = 1e5 + 5;
using namespace TREE;
using PRE::Min;
using PRE::rank;
inline void add(const int &now, const int &tag)
{
//now 是节点编号 tag 是操作类型
int k = w[now], cnt = 0;
static int a[23], p[23];
while (k > 1)
{
int f = Min[k];
a[++cnt] = 0;
p[cnt] = f;
while (k % f == 0)
k /= f, ++a[cnt];
}
for (int t = 1; t <= cnt; ++t)
{
if (((int)s[rank[p[t]]].size()) <= 1 + a[t])
s[rank[p[t]]].resize(a[t] + 2);
s[rank[p[t]]][a[t]] += tag;
}
}
inline void que(const int &now, const int &id)
{
//now 是询问编号
int k = W[now > 0 ? now : -now], cnt = 0, ret = 1;
static int a[23], p[23];
while (k > 1)
{
int f = Min[k];
a[++cnt] = 0;
p[cnt] = f;
while (k % f == 0)
k /= f, ++a[cnt];
}
for (int t = 1; t <= cnt; ++t)
for (int i = 1, ed = s[rank[p[t]]].size(); i < ed; ++i)
ret = 1ll * ret * ksm(p[t], 1ll * s[rank[p[t]]][i] * min(a[t], i) % (mod - 1)) % mod;
if (now < 0)
ans[-now] = 1ll * ans[-now] * inv(ret) % mod * inv(ret) % mod * __gcd(W[-now], w[id]) % mod;
else
ans[now] = 1ll * ans[now] * ret % mod;
}
void dfs(const int &now, const int &last)
{
add(now, 1);
for (auto t : q[now])
que(t, now);
for (auto t : e[now])
if (t ^ last)
dfs(t, now);
add(now, -1);
}
} // namespace sol
int main()
{
PRE::pre(1e7);
n = qr();
for (int t = 2; t <= n; ++t)
TREE::add(qr(), qr());
for (int t = 1; t <= n; ++t)
TREE::w[t] = qr();
TREE::init(n);
m = qr();
for (int t = 1, t1, t2, t3; t <= m; ++t)
{
t1 = qr();
t2 = qr();
t3 = qr();
TREE::addq(t1, t2, t, t3);
}
sol::dfs(1, 0);
for (int t = 1; t <= m; ++t)
printf("%d\n", TREE::ans[t]);
return 0;
}
Raw
e.zjk.cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <queue>
using namespace std;
template <typename T>
void chkmax(T &x, T y) { x = x > y ? x : y; }
template <typename T>
void chkmin(T &x, T y) { x = x > y ? y : x; }
typedef long long ll;
typedef unsigned long long ull;
const int INF = 2139062143;
#define DEBUG(x) std::cerr << #x << " = " << x << std::endl
template <typename T>
void read(T &x)
{
x = 0;
bool f = 1;
char ch;
do
{
ch = getchar();
if (ch == '-')
f = 0;
} while (ch > '9' || ch < '0');
do
{
x = x * 10 + ch - '0';
ch = getchar();
} while (ch >= '0' && ch <= '9');
x = f ? x : -x;
}
template <typename T>
void write(T x)
{
if (x < 0)
x = ~x + 1, putchar('-');
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
const int N = 1e5 + 7;
const int P = 1e6 + 7;
const int M = 1e7 + 5;
const int mod = 1e9 + 7;
const int LOG = 20 + 5;
int n, m, a[N], w[N], ans[N];
vector<int> q[N];
namespace LCA
{
int E, dep[N], head[N], f[N][LOG];
struct EDGE
{
int to, nxt;
} edge[N << 1];
inline void addedge(int u, int v)
{
edge[++E].to = v;
edge[E].nxt = head[u];
head[u] = E;
}
inline void dfs(int u, int fa)
{
dep[u] = dep[fa] + 1;
f[u][0] = fa;
for (int i = 1; i <= 20; i++)
f[u][i] = f[f[u][i - 1]][i - 1];
for (int i = head[u]; i; i = edge[i].nxt)
{
int v = edge[i].to;
if (v == fa)
continue;
dfs(v, u);
}
}
inline int lca(int u, int v)
{
if (dep[u] < dep[v])
swap(u, v);
for (int i = 20; i >= 0; i--)
{
if (dep[f[u][i]] >= dep[v])
u = f[u][i];
if (u == v)
return u;
}
if (u == v)
return u;
for (int i = 20; i >= 0; i--)
{
if (f[u][i] != f[v][i])
{
u = f[u][i];
v = f[v][i];
}
}
return f[u][0];
}
} // namespace LCA
namespace PRIME
{
int cnt, prime[P];
bool vis[M];
inline void init(int NN)
{
for (int i = 2; i <= NN; i++)
{
if (!vis[i])
{
prime[++cnt] = i;
}
for (int j = 1; j <= cnt && prime[j] * i <= NN; j++)
{
vis[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
}
} // namespace PRIME
namespace solve
{
using namespace LCA;
int cnt[P][LOG];
inline int qpow(int a, int b)
{
int ret = 1;
while (b)
{
if (b & 1)
ret = 1ll * ret * a % mod;
// assert(ret >= 0);
a = 1ll * a * a % mod;
// assert(a >= 0);
b >>= 1;
}
return ret % mod;
}
inline void add(int val, int opt)
{
for (int i = 1; 1ll * PRIME::prime[i] * PRIME::prime[i] <= val && i <= PRIME::cnt; i++)
{
if (val % PRIME::prime[i])
continue;
int p = 0;
while (val % PRIME::prime[i] == 0)
{
val /= PRIME::prime[i];
p++;
}
cnt[i][p] += opt;
}
if (val != 1)
{
int pos = lower_bound(PRIME::prime + 1, PRIME::prime + PRIME::cnt + 1, val) - PRIME::prime;
cnt[pos][1] += opt;
}
}
inline int gcd(int x, int y)
{
if (x < y)
swap(x, y);
return y == 0 ? x : gcd(y, x % y);
}
inline int sqr(int x)
{
return 1ll * x * x % mod;
}
inline int query(int val)
{
int ans = 1;
for (int i = 1; 1ll * PRIME::prime[i] * PRIME::prime[i] <= val && i <= PRIME::cnt; i++)
{
if (val % PRIME::prime[i])
continue;
int p = 0;
while (val % PRIME::prime[i] == 0)
{
val /= PRIME::prime[i];
p++;
}
int s = 0;
for (int j = 1; j <= p; j++)
s += cnt[i][j] * j;
for (int j = p + 1; j < LOG; j++)
s += cnt[i][j] * p;
ans = 1ll * ans * qpow(PRIME::prime[i], s) % mod;
}
if (val != 1)
{
int pos = lower_bound(PRIME::prime + 1, PRIME::prime + PRIME::cnt + 1, val) - PRIME::prime;
int s = 0;
for (int j = 1; j < LOG; j++)
s += cnt[pos][j];
ans = 1ll * ans * qpow(val, s) % mod;
}
return (ans % mod + mod) % mod;
}
inline void dfs(int u, int f)
{
add(a[u], 1);
for (int i = 0, sz = q[u].size(); i < sz; i++)
{
int id = q[u][i];
int x = query(w[abs(id)]);
if (id > 0)
ans[id] = 1ll * ans[id] % mod * x % mod;
if (id < 0)
ans[-id] = 1ll * ans[-id] % mod * qpow(1ll * x * x % mod, mod - 2) % mod * gcd(w[-id], a[u]) % mod;
}
for (int i = head[u]; i; i = edge[i].nxt)
{
int v = edge[i].to;
if (v == f)
continue;
dfs(v, u);
}
add(a[u], -1);
}
} // namespace solve
int main()
{
read(n);
PRIME::init(1e7);
for (int i = 1, u, v; i < n; i++)
{
read(u);
read(v);
LCA::addedge(u, v);
LCA::addedge(v, u);
}
LCA::dfs(1, 0);
for (int i = 1; i <= n; i++)
read(a[i]);
read(m);
for (int i = 1, x, y, z; i <= m; i++)
{
read(x);
read(y);
read(z);
int LCA = LCA::lca(x, y);
w[i] = z;
ans[i] = 1;
q[LCA].push_back(-i);
q[x].push_back(i);
q[y].push_back(i);
}
solve::dfs(1, 0);
for (int i = 1; i <= m; i++)
printf("%d\n", (ans[i] % mod + mod) % mod);
return 0;
}
Raw
f.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
namespace Math
{
const int N = 31622800;
const int MX = 1952000;
bool notPrime[N];
int prime[MX], primeCnt = 0;
inline void sieve()
{
notPrime[1] = true;
for (int i = 2; i < N; ++i)
{
if (!notPrime[i])
{
prime[++primeCnt] = i;
}
for (int j = 1, p; j <= primeCnt; ++j)
{
p = prime[j];
if (i * p >= N)
{
break;
}
notPrime[i * p] = true;
if (i % p == 0)
{
break;
}
}
}
}
ll fac[20], facTop = 0;
inline void factor(ll x)
{
facTop = 0;
for (int i = 1, p; i <= primeCnt; ++i)
{
p = prime[i];
if ((ll)p * p > x)
{
break;
}
if (x % p == 0)
{
do
{
x /= p;
} while (x % p == 0);
fac[++facTop] = p;
}
}
if (x != 1)
{
fac[++facTop] = x;
}
}
} // namespace Math
namespace G
{
const int N = 1e5 + 5;
ll dis[N];
inline void dijkstra()
{
memset(dis, 0x3f, sizeof(dis));
priority_queue<pair<ll, int>> q;
dis[0] = 0LL;
q.emplace((pair<ll, int>){0LL, 0});
while (!q.empty())
{
auto p = q.top();
q.pop();
ll w = p.first;
int u = p.second;
if (w == dis[u])
{
for (int i = 2, v; i <= Math::facTop; ++i)
{
v = (u + Math::fac[i]) % Math::fac[1];
if (dis[v] > w + Math::fac[i])
{
dis[v] = w + Math::fac[i];
q.emplace((pair<ll, int>){dis[v], v});
}
}
}
}
}
} // namespace G
inline int inv(ll x, int MOD)
{
int base = x % MOD, exp = MOD - 2, res = 1;
while (exp != 0)
{
if (exp & 1)
{
res = (ll)res * base % MOD;
}
base = (ll)base * base % MOD;
exp >>= 1;
}
return res;
}
const int N = 1e4 + 5;
int T;
struct Query
{
ll n, k;
int id;
inline const bool operator<(const Query &rhs) const
{
return k < rhs.k;
}
};
Query query[N];
bool ans[N];
int main()
{
Math::sieve();
read(T);
ll n, k;
for (int cas = 1; cas <= T; ++cas)
{
read(n), read(k);
query[cas] = (Query){n, k, cas};
}
sort(query + 1, query + T + 1);
for (int i = 1, fac; i <= T; ++i)
{
n = query[i].n, k = query[i].k;
if (k == 1)
{
ans[query[i].id] = false; // unnecessary
}
else
{
if (k != query[i - 1].k)
{
Math::factor(k);
fac = Math::facTop;
if (fac > 2)
{
G::dijkstra();
}
}
if (fac == 1)
{
ans[query[i].id] = (bool)(n % Math::fac[1] == 0);
}
else if (fac == 2)
{
ll a = Math::fac[1], b = Math::fac[2];
int y = n % a * inv(b, a) % a;
ans[query[i].id] = (bool)(b * y <= n);
}
else
{
ans[query[i].id] = (bool)(G::dis[n % Math::fac[1]] <= n);
}
}
}
for (int i = 1; i <= T; ++i)
{
puts(ans[i] ? "YES" : "NO");
}
}
Raw
f.debug.cpp
#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
<< (#x) << ": " << x << std::endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename Tp>
inline void read(Tp &x)
{
static char c;
static bool neg;
x = 0, c = getchar(), neg = false;
for (; !isdigit(c); c = getchar())
{
if (c == '-')
{
neg = true;
}
}
for (; isdigit(c); c = getchar())
{
x = x * 10 + c - '0';
}
if (neg)
{
x = -x;
}
}
namespace Math
{
const int N = 31622800;
const int MX = 1952000;
bool notPrime[N];
int prime[MX], primeCnt = 0;
inline void sieve()
{
notPrime[1] = true;
for (int i = 2; i < N; ++i)
{
if (!notPrime[i])
{
prime[++primeCnt] = i;
}
for (int j = 1, p; j <= primeCnt; ++j)
{
p = prime[j];
if (i * p >= N)
{
break;
}
notPrime[i * p] = true;
if (i % p == 0)
{
break;
}
}
}
}
ll fac[20], facTop = 0;
inline void factor(ll x)
{
facTop = 0;
for (int i = 1, p; i <= primeCnt; ++i)
{
p = prime[i];
if ((ll)p * p > x)
{
break;
}
if (x % p == 0)
{
do
{
x /= p;
} while (x % p == 0);
fac[++facTop] = p;
}
}
if (x != 1)
{
fac[++facTop] = x;
}
}
} // namespace Math
namespace G
{
const int N = 1e5 + 5;
ll dis[N];
inline void dijkstra()
{
memset(dis, 0x3f, sizeof(dis));
priority_queue<pair<ll, int>> q;
dis[0] = 0LL;
q.emplace((pair<ll, int>){0LL, 0});
while (!q.empty())
{
auto p = q.top();
q.pop();
ll w = p.first;
int u = p.second;
if (w == dis[u])
{
for (int i = 2, v; i <= Math::facTop; ++i)
{
v = (u + Math::fac[i]) % Math::fac[1];
if (dis[v] > w + Math::fac[i])
{
dis[v] = w + Math::fac[i];
q.emplace((pair<ll, int>){dis[v], v});
}
}
}
}
}
} // namespace G
inline int inv(ll x, int MOD)
{
int base = x % MOD, exp = MOD - 2, res = 1;
while (exp != 0)
{
if (exp & 1)
{
res = (ll)res * base % MOD;
}
base = (ll)base * base % MOD;
exp >>= 1;
}
return res;
}
const int N = 1e4 + 5;
int T;
struct Query
{
ll n, k;
int id;
inline const bool operator<(const Query &rhs) const
{
return k < rhs.k;
}
};
Query query[N];
bool ans[N];
int main()
{
Math::sieve();
read(T);
ll n, k;
for (int cas = 1; cas <= T; ++cas)
{
read(n), read(k);
query[cas] = (Query){n, k, cas};
}
sort(query + 1, query + T + 1);
for (int i = 1, fac; i <= T; ++i)
{
n = query[i].n, k = query[i].k;
if (k == 1)
{
ans[query[i].id] = false; // unnecessary
}
else
{
if (k != query[i - 1].k)
{
Math::factor(k);
fac = Math::facTop;
if (fac > 2)
{
G::dijkstra();
}
}
if (fac == 1)
{
watch(1);
ans[query[i].id] = (bool)(n % Math::fac[1] == 0);
}
else if (fac == 2)
{
watch(2);
watch(Math::fac[1]), watch(Math::fac[2]);
ll a = Math::fac[1], b = Math::fac[2];
int y = n % a * inv(b, a) % a;
watch((ll)b * y);
ans[query[i].id] = (bool)(b * y <= n);
}
else
{
watch(3);
ans[query[i].id] = (bool)(G::dis[n % Math::fac[1]] <= n);
}
}
}
for (int i = 1; i <= T; ++i)
{
puts(ans[i] ? "YES" : "NO");
}
}
Raw
f.hxb.cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
int read()
{
char x = getchar();
int ans = 0, flag = 1;
while (!isdigit(x))
if (x == '-')
flag = -1, x = getchar();
else
x = getchar();
while (isdigit(x))
ans = ans * 10 + x - '0', x = getchar();
return ans * flag;
}
const int N = sqrt(1e15) + 10;
bool is_prime[N + 5];
int prime[2000005], cnt;
void check()
{
for (int i = 2; i <= N; i++)
{
if (!is_prime[i])
prime[++cnt] = i;
for (int j = 1; j <= cnt; j++)
{
if (prime[j] * i > N)
break;
is_prime[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
}
struct node
{
int id, n, k;
bool operator<(node x) const
{
return k < x.k;
}
} Q[10005];
int q, dis[100005];
map<int, int> mp;
vector<int> V;
void dijkstra()
{
memset(dis, 0x3f, sizeof(dis));
priority_queue<pair<int, int>> q;
q.push(make_pair(0, 0));
dis[0] = 0;
while (!q.empty())
{
pair<int, int> x = q.top();
q.pop();
int u = x.second, w = x.first;
if (w != dis[u])
continue;
for (int i = 1; i < V.size(); i++)
{
int v = (u + V[i]) % V[0];
if (dis[v] > w + V[i])
{
dis[v] = w + V[i];
q.push(make_pair(dis[v], v));
}
}
}
}
int ans[10005];
int ksm(int a, int p, int mod)
{
int ans = 1;
while (p)
{
if (p & 1)
ans = ans * a % mod;
a = a * a % mod;
p >>= 1;
}
return ans;
}
signed main()
{
check();
q = read();
for (int i = 1; i <= q; i++)
{
int n = read(), k = read();
Q[i] = node{i, n, k};
}
sort(Q + 1, Q + q + 1);
for (int i = 1; i <= q; i++)
{
if (Q[i].k == 1)
{
ans[Q[i].id] = 0;
continue;
}
if (Q[i].k != Q[i - 1].k)
{
V.clear();
mp[Q[i].k] = 0;
int k = Q[i].k;
for (int j = 1; prime[j] * prime[j] <= k && j <= cnt; j++)
{
if (k % prime[j] == 0)
{
mp[Q[i].k]++;
V.push_back(prime[j]);
while (k % prime[j] == 0)
k /= prime[j];
}
}
if (k != 1)
mp[Q[i].k]++, V.push_back(k);
if (mp[Q[i].k] > 2)
dijkstra();
}
if (mp[Q[i].k] == 1)
{
if (Q[i].n % V[0] == 0)
ans[Q[i].id] = 1;
else
ans[Q[i].id] = 0;
}
if (mp[Q[i].k] == 2)
{
int tmp = V[1] % V[0];
int tmpp = ksm(tmp, V[0] - 2, V[0]);
int tmppp = Q[i].n % V[0];
int anss = (tmpp * tmppp) % V[0] * V[1];
if (anss <= Q[i].n)
ans[Q[i].id] = 1;
else
ans[Q[i].id] = 0;
}
if (mp[Q[i].k] > 2)
{
int u = Q[i].n % V[0];
if (dis[u] <= Q[i].n)
ans[Q[i].id] = 1;
else
ans[Q[i].id] = 0;
}
}
for (int i = 1; i <= q; i++)
{
if (ans[i])
puts("YES");
else
puts("NO");
}
return 0;
}
Raw
f.primeCnt.cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 5;
bool notPrime[N];
vector<int> primes;
inline void sieve()
{
primes.reserve(N / 10);
for (int i = 2; i < N; ++i)
{
if (!notPrime[i])
{
primes.emplace_back(i);
}
for (const auto &p : primes)
{
if (i * p >= N)
{
break;
}
notPrime[i * p] = true;
if (i % p == 0)
{
break;
}
}
}
}
int main()
{
sieve();
cout << primes.size() << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment