• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

3小时前 1次浏览

# 2021.7.19模拟赛

## 比赛概括：

(mathrm{sum}=8+80+0+0)

## T2 最大公约数：

### 代码：

``````
const int N = 1e6 + 10;

{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}

bool vis[N];
int pri[N], phi[N], cnt, sum[N];
void Prime()
{
phi[1] = 1;
for (int i = 2; i <= N - 10; i++)
{
if (!vis[i]) pri[++cnt] = i, phi[i] = i - 1;
for (int j = 1; j <= cnt && i * pri[j] <= N - 10; j++)
{
vis[i * pri[j]] = 1;
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
if (!(i % pri[j])) {phi[i * pri[j]] = phi[i] * pri[j]; break;}
}
}
for (int i = 1; i <= N - 10; i++)
sum[i] = sum[i - 1] + phi[i];
}

int t, n;
ll ans;

int main()
{
Prime();
for (t = Read(); t--; )
{
ans = 0;
for (int l = 1, r; l <= n; l = r + 1)
{
r = n / (n / l);
ans += (2 * sum[n / l] - 1) * ((l + r) * (r - l + 1) / 2);
}
ans -= n * (n + 1) / 2;
ans /= 2;
printf ("%lldn", ans);
}
return 0;
}
``````

## T3 「JOI 2020 Final」只不过是长的领带：

### 代码：

``````const int N = 2e5 + 10;

{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}

int n;
struct node
{
ll val, id;
bool operator < (const node &a) const
{
return val < a.val;
}
}a[N];
ll b[N], c[N], ans;
ll mx[N];

int main()
{
for (int i = 0; i <= n; i++)
a[i] = (node) {Read(), i};
for (int i = 1; i <= n; i++)
sort (a, a + 1 + n);
sort (b + 1, b + 1 + n);
for (int i = 1; i <= n; i++)
ans = max(ans, max(0ll, a[i].val - b[i]));
c[a[0].id] = ans;
for (int i = n; i; i--)
mx[i] = max(mx[i + 1], max(0ll, a[i].val - b[i]));
ans = 0;
for (int i = 1; i <= n; i++)
{
swap(a[0], a[i]);
ans = max(ans, max(0ll, a[i].val - b[i]));
c[a[0].id] = max(ans, mx[i + 1]);
}
for (int i = 0; i <= n; i++)
printf ("%lld ", c[i]);
return 0;
}
``````