Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin("numere.in");
- ofstream fout("numere.out");
- bool isPrime(int a) {
- if(a == 3)
- return true;
- if(a % 3 == 0)
- return false;
- int rad = sqrt(a);
- for(int i = 5; i <= rad; i += 6)
- if(a % i == 0 || a % (i + 2) == 0)
- return false;
- return true;
- }
- int main() {
- fin.sync_with_stdio(false);
- fout.sync_with_stdio(false);
- fin.tie(nullptr);
- fout.tie(nullptr);
- int task, N;
- fin >> task >> N;
- vector<int> primes;
- primes.emplace_back(2);
- for(int i = 3; i < 333; i += 2)
- if(isPrime(i))
- primes.emplace_back(i);
- vector<int> vals(N + 1);
- int mx = 0, val = 0, sz = primes.size();
- for(int i = 1; i <= N; ++i) {
- int P = 1, x = i, d = 0;
- while(x > 1 && d < sz) {
- int e = 0;
- while(x % primes[d] == 0) {
- x /= primes[d];
- ++e;
- }
- P *= (e + 1);
- ++d;
- }
- if(x > 1)
- P *= 2;
- vals[i] = P - 2;
- if(i == 1)
- vals[1] = 0;
- if(vals[i] > mx) {
- mx = vals[i];
- val = i;
- }
- }
- if(task == 1) {
- fout << val;
- return 0;
- }
- int M, T;
- fin >> M >> T;
- vector<int> sum(N + 1);
- for(int i = 1; i <= N; ++i)
- sum[i] = sum[i - 1] + (vals[i] == T);
- long long ans = 0;
- for(int i = 1; i <= N; ++i) {
- int st = i + 1, dr = N, p1 = i;
- while(st <= dr) {
- int mid = (st + dr) >> 1;
- if(sum[mid] - sum[i - 1] >= M) {
- p1 = mid;
- dr = mid - 1;
- }
- else
- st = mid + 1;
- }
- st = i + 1, dr = N;
- int p2 = i;
- while(st <= dr) {
- int mid = (st + dr) >> 1;
- if(sum[mid] - sum[i - 1] <= M) {
- p2 = mid;
- st = mid + 1;
- }
- else
- dr = mid - 1;
- }
- if(sum[p1] - sum[i - 1] == M && sum[p2] - sum[i - 1] == M)
- ans += p2 - p1 + 1;
- }
- fout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement