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 20000
#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';
}
