Thanks you for participating in TheForces Round #4! Here is editorial:
[problem:422264A]
Answer is $$$floor(sqrt(r)) — floor(sqrt(l — 1))$$$.
Alternatively you can use binary search to calculate square root.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int get(int r) {
int tt = 0;
for (int uu = r; uu >= 1; uu /= 2)
while ((tt + uu) * (tt + uu) <= r)
tt += uu;
return tt;
}
int32_t main() {
iostream::sync_with_stdio(0); cin.tie(0);
int q; cin >> q;
while (q--) {
int l, r; cin >> l >> r;
cout << get(r) - get(l - 1) << '\n';
}
}
[problem:422264B]
You always can make all bits less or equal to the most significant bit set to $$$1$$$. Also you cant make most significant bit greater.
Just go through numbers and find the minimal most significant bit.
Answer is number with all bits less or equal to minimal most significant bit set to $$$1$$$.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
iostream::sync_with_stdio(0); cin.tie(0);
int q; cin >> q;
while (q--) {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int bb = a[0];
for (int i = 0; i < n; i++) {
int tt = 0;
while (a[i] / (1ll << (tt + 1)) > 0)
tt++;
bb = min(bb, tt);
}
cout << (1ll << (bb + 1)) - 1 << '\n';
}
}
[problem:422264C]
Best way to choose the integer is the $$$gcd$$$ of all elements in the array except for element you want to change.
So you just need to calculate the $$$gcd$$$ of all elements in the array except for one in some fast way.
You can use pre-calculated prefix/suffix $$$gcd$$$ to do it.
Also take care about the case $$$n = 1$$$, The answer for this case will be always $$$10^9$$$.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
iostream::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
if (n == 1) {
int a; cin >> a;
cout << 1000000000;
return 0;
}
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> pp(n), ss(n);
pp[0] = a[0];
ss[n - 1] = a[n - 1];
for (int i = 1; i < n; i++)
pp[i] = __gcd(pp[i - 1], a[i]);
for (int i = n - 2; i >= 0; i--)
ss[i] = __gcd(ss[i + 1], a[i]);
int bb = max(ss[1], pp[n - 2]);
for (int i = 1; i < n - 1; i++)
bb = max(bb, __gcd(pp[i - 1], ss[i + 1]));
cout << bb;
}
[problem:422264D]
We can imagine that Alice and Bob are on different sides of the river. It's obvious that in this case best path is just straight line between Alice and Bob.
So you can just negate $$$y$$$ coordinate for Bob and calculate the Euclidean distance of the obtained point with the other point, It can be proven that the obtained distance is the shortest possible.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
iostream::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) {
long double x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
y2 = -y2;
cout << fixed << sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) << '\n';
}
}
[problem:422264E]
It's obvious that you can change bases in original formula to their last digits.
After you can just check some cases.
$$$1^{10x+1}$$$ mod $$$10$$$ is always $$$1$$$
$$$2^{10x+2}$$$ mod $$$10$$$ is switching between $$$4$$$ and $$$6$$$
$$$3^{10x+3}$$$ mod $$$10$$$ is switching between $$$7$$$ and $$$3$$$
$$$4^{10x+4}$$$ mod $$$10$$$ is always $$$6$$$
$$$5^{10x+5}$$$ mod $$$10$$$ is always $$$5$$$
$$$6^{10x+6}$$$ mod $$$10$$$ is always $$$6$$$
$$$7^{10x+7}$$$ mod $$$10$$$ is switching between $$$3$$$ and $$$7$$$
$$$8^{10x+8}$$$ mod $$$10$$$ is switching between $$$6$$$ and $$$4$$$
$$$9^{10x+9}$$$ mod $$$10$$$ is always $$$9$$$
$$$0^{10x+0}$$$ mod $$$10$$$ is always $$$0$$$
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
iostream::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
int ss = 0;
for (int x = 1; x <= 10; x++) {
int aa = n / 10 + ((n % 10) >= x);
if (x == 4)
ss = (ss + 6 * aa) % 10;
else if (x == 2)
ss = (ss + (4 * ((aa + 1) / 2) + 6 * (aa / 2))) % 10;
else if (x == 3)
ss = (ss + (7 * ((aa + 1) / 2) + 3 * (aa / 2))) % 10;
else if (x == 7)
ss = (ss + (3 * ((aa + 1) / 2) + 7 * (aa / 2))) % 10;
else if (x == 8)
ss = (ss + (6 * ((aa + 1) / 2) + 4 * (aa / 2))) % 10;
else
ss = (ss + x * aa) % 10;
}
cout << ss << '\n';
}
}
[problem:422264F]
First, we need to write sieve for finding primes to $$$sqrt(a_i)$$$ it means $$$10^4$$$ to solve problem faster, then find prime divisors of number $$$k$$$ and their count.
If $$$N=p^a*q^b*r^c$$$ .
Number of divisors = $$$(a+1)*(b+1)*(c+1)$$$,
Sum of divisors = $$$(p^0+p^1+p^2......p^a)(q^0+q^1+q^2......q^b)(r^0+r^1+r^2......r^c)$$$ .
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 10001
#define M 1000000007
vector<int> pp;
bool prime[N];
void init() {
for (int i = 0; i < N; i++)
prime[i] = true;
for (int i = 2; i < N; i++) {
if (!prime[i])
continue;
pp.push_back(i);
for (int j = i * i; j < N; j += i)
prime[j] = false;
}
}
int32_t main() {
iostream::sync_with_stdio(0); cin.tie(0);
init();
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
map<int, int> mp;
for (int i = 0; i < n; i++) {
for (int x : pp)
while (a[i] % x == 0) {
a[i] /= x;
mp[x]++;
}
if (a[i] > 1)
mp[a[i]]++;
}
int aa = 1;
int bb = 1;
for (auto [x, y] : mp) {
aa = (aa * (y + 1)) % M;
int vv = bb;
bb = 0;
for (int i = 0; i <= y; i++) {
bb = (bb + vv) % M;
vv = (vv * x) % M;
}
}
cout << aa << ' ' << bb << '\n';
}
}
[problem:422264G]
If you already calculated answer for $$$n$$$ — $$$1$$$, you can find answer for $$$n$$$ in next way:
You already have calculated answer for all subsets without $$$n$$$.
Now you want to find answer for all new subsets.
It's obvious that all new subsets are old subsets but with $$$n$$$ in them.
So for all subsets you want to change answer from $$$\frac{f}{s}$$$ to $$$\frac{f + n}{s * n}$$$.
$$$\frac{f + n}{s * n} = \frac{f}{s}/n + \frac{n}{s}/n = \frac{ans_{old}}{n} + \frac{1}{s}$$$.
So you want to keep sum of $$$\frac{1}{s}$$$ and sum of $$$\frac{f}{s}$$$ over all subsets
Let sum of $$$\frac{1}{s}$$$ be $$$Y$$$ and sum of $$$\frac{f}{s}$$$ be $$$X$$$
When you add $$$n$$$, $$$Y$$$ changes to $$$Y + Y/n$$$, and $$$X$$$ changes to $$$X + X/n + Y$$$
Final answer is $$$X$$$
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
iostream::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
long double x = 0, y = 1;
for (int i = 1; i <= n; i++) {
x += x / i + y;
y += y / i;
}
cout << fixed << x << '\n';
}
