# [2018 Multi-University Training Contest 10] C. Calculate

### Statement：

Given $1 \leq A, B, C \leq 10^7$, compute

$\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \phi(\gcd(i, j^2, k^3))$

no more than 10 test cases.

### Solution：

Consider the number of triples (i, j, k) such that $\gcd(i, j^2, k^3) = d$, denoted as $f(d)$. By Mobius inversion,

$f(d) = \sum_{i} \mu(i) g(di)$

where $g(d)$ is the number of triples satisfying $d | \gcd(i, j^2, k^3)$, and the answer should be

$\sum_{d=1}^A f(d) \phi(d)$

Now we try to compute $g(d)$:

$g(d) = \sum_{i = 1}^A [d | i] \sum_{j = 1}^B [d | j^2] \sum_{k = 1}^C [d | k^3]$

Let $d = \prod {p_i}^{a_i}$ denote the unique factorization of d. Note that $d | k^n$ whenever $\prod {p_i}^{\lceil a_i / n \rceil} | k$.

Let $h_n(d) = \prod {p_i}^{\lceil a_i / n \rceil}$, which denotes the minimum positive integer whose nth power is divisible by d. Now $g(d)$ could be rewritten as

$g(d) = \lfloor \frac{A}{d} \rfloor \lfloor \frac{B}{h_2(d)} \rfloor \lfloor \frac{C}{h_3(d)} \rfloor$

$\sum_{d=1}^A f(d) \phi(d) = \sum_{d=1}^A \phi(d) \sum_{i} \mu(i) g(di) = \sum_{q = 1}^A g(q) \sum_{ij = q} \mu(i) \phi(j)$

where the Dirichlet convolution $(\mu * \phi)(q) = \sum_{ij = q} \mu(i) \phi(j)$ is multiplicative and thus could be effectively precomputed (along with $h_2$, $h_3$) by the sieve of Euler in linear time. Hence each test case could be done in $O(A)$ time.

### Source Code:

#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
__func__, ##__VA_ARGS__)
#else
# define _debug(...) ((void) 0)
#endif
#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

namespace sieve {
constexpr int MAXN = 10000007;
bool p[MAXN];
int prime[MAXN], sz;
int pval[MAXN], pcnt[MAXN];
unsigned h2[MAXN], h3[MAXN], phi[MAXN], muphi[MAXN];

void exec(int N = 10000007) {
p[0] = p[1] = 1;

pval[1] = 1;
pcnt[1] = 0;
h2[1] = h3[1] = phi[1] = muphi[1] = 1;

for (int i = 2; i < N; i++) {
if (!p[i]) {
prime[sz++] = i;
for (LL j = i; j < N; j *= i) {
int b = j / i;
pval[j] = i * pval[b];
pcnt[j] = pcnt[b] + 1;
h2[j] = h2[b] * (pcnt[j] % 2 == 1 ? i : 1);
h3[j] = h3[b] * (pcnt[j] % 3 == 1 ? i : 1);
phi[j] = (i == j ? i-1 : phi[b] * i);
muphi[j] = phi[j] - phi[b];
}
}
for (int j = 0; i * prime[j] < N; j++) {
int x = i * prime[j]; p[x] = 1;
if (i % prime[j] == 0) {
pval[x] = pval[i] * prime[j];
pcnt[x] = pcnt[i] + 1;
} else {
pval[x] = prime[j];
pcnt[x] = 1;
}
if (x != pval[x]) {
int b = x / pval[x];
h2[x] = h2[b] * h2[pval[x]];
h3[x] = h3[b] * h3[pval[x]];
muphi[x] = muphi[b] * muphi[pval[x]];
}
if (i % prime[j] == 0) break;
}
}
}
}

int main() {
using namespace sieve;
exec();
int T; scanf("%d", &T);
while (T--) {
unsigned a, b, c; scanf("%d%d%d", &a, &b, &c);
unsigned res = 0;
for (unsigned i = 1; i <= a; i++)
res += muphi[i] * (a / i) * (b / h2[i]) * (c / h3[i]);
printf("%d\n", res & 0x3fffffff);
}
return 0;
}


# 题解：

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i <=(n); i++)
#define range(x) begin(x), end(x)

typedef complex<double> pt, vec;
typedef pair<pt, pt> seg;

const double EPS = 1e-8;
int fcmp(double a, double b = 0.0) {
if (fabs(a - b) < EPS) return 0;
return a < b ? -1 : 1;
}

double operator * (pt a, pt b) {
return a.real() * b.imag() - a.imag() * b.real();
}

double operator , (pt a, pt b) {
return a.real() * b.real() + a.imag() * b.imag();
}

inline bool ptOnSeg(pt p, seg s){
vec v1 = s.first - p, v2 = s.second - p;
return fcmp((v1, v2)) <= 0 && fcmp(v1 * v2) == 0;
}

inline pt getIntersection(pt P, vec v, pt Q, vec w) {
return P + v * (w*(P-Q)/(v*w));
}

// -1 outside the polygon
// 0  on the border of the polygon
// 1  inside the polygon
int ptOnPoly(pt p, pt* poly, int n){
//  fprintf(stderr, "(%.7f, %.7f)\n", p);
int wn = 0;
for (int i = 0; i < n; i++){
if (ptOnSeg(p, {poly[i], poly[i+1]})) return 0;
int d1 = fcmp(poly[i].imag() - p.imag()),
d2 = fcmp(poly[i+1].imag() - p.imag()),
k = fcmp((poly[i+1] - poly[i])*(p - poly[i]));
if (k > 0 && d1 <= 0 && d2 > 0) wn++;
if (k < 0 && d2 <= 0 && d1 > 0) wn--;
}
return wn ? 1 : -1;
}

istream& operator >> (istream& lhs, pt& rhs){
double x, y;
lhs >> x >> y;
rhs = {x, y};
return lhs;
}

int n;
vector<pt> poly;
double ans = 0.0;

void attempt(pt a, pt b) {
vector<pt> points;
rep (i, n)
if (fcmp((b-a)*(poly[i]-a)) * fcmp((b-a)*(poly[i+1]-a)) <= 0) {
auto vec1 = b-a, vec2 = poly[i+1] - poly[i];
if (fcmp(vec1 * vec2) == 0) {
points.push_back(poly[i]);
points.push_back(poly[i+1]);
} else {
points.push_back(getIntersection(a, b-a, poly[i], poly[i+1]-poly[i]));
}
}
sort(range(points), [] (pt a, pt b) {
return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
});
points.resize(unique(range(points), [] (pt a, pt b) {
return fcmp(a.real(), b.real()) == 0 && fcmp(a.imag(), b.imag()) == 0;
}) - points.begin());
double cur = 0.0;
assert(points.size() > 1);
for (int i = 1; i < points.size(); i++) {
if (ptOnPoly((points[i]+points[i-1]) / 2.0, poly.data(), n) >= 0) {
cur += abs(points[i] - points[i-1]);
} else {
cur = 0.0;
if (abs(points.back() - points[i]) <= ans) return;
}
ans = max(ans, cur);
}
}

int main() {
cin >> n; poly.resize(n);
rep (i, n) cin >> poly[i];
poly.push_back(poly[0]);
rep (i, n) {
rep (j, i) {
attempt(poly[i], poly[j]);
}
}
printf("%.8f\n", ans);
return 0;
}


# 2018牛客暑期ACM多校训练营（第一场）题解

### A. Monotonic Matrix

• $a_{i,j} \in \{0, 1, 2\}$
• 每一行从左到右和每一列从上到下单调不减

### F. Sum of Maximum

$\sum_{x_1=1}^{a_1} \sum_{x_2=1}^{a_1} \cdots \sum_{x_n=1}^{a_n} \max\{x_1, x_2, \cdots, x_n\}$

# 2017-2018 问题求解（四）上机考试题解

## Day1

#### A 差异度

1. 注意到当$n$很大时，最终答案不会太大（考虑一个01串hamming距离为$d$的邻域大小随$d$是指数增长的，然后用鸽巢原理即可）。所以，从小到大枚举答案$d$，并在每个串的$d$-邻域内搜索即可。
2. 建图。将所有20位的01串视为顶点，相差1位的两个串连边。问题就变成了：给定一个顶点子集，求这个子集中两两距离的最小值。这用多线程bfs就可以解决。时间复杂度为$2^{20}*20$。
3. 用FWT处理出所有可能的异或值，取popcount最小的那个即可。（FWT课内没学，用了感觉有点犯规，但写起来方便是真的

B 旅行箱

# 2018 ACM-ICPC China Jiangsu Provincial Programming Contest

A. 签到题

B. 滚动数组DP

C. ???

D. $\frac{(\sum_{i=1}^n U[i])!}{\prod_{i=1}^n U[i]!}$

E. Catalan数？

F. 预处理dfs序，按照F的值的顺序更新树状数组求方案数

G. 每M个数分为一组，组内求出所有前缀积和后缀积。每个window就可以拆成一个前缀积和一个后缀积的乘积。

H. Berlekamp-Massey模板题

I. 将矩阵乘法的定义中，乘法改为加法，加法改为max，然后求个矩乘快速幂

J. 高精度

K. 求出最短路图中除起点外所有点的入度之积