Аврора Интенсив день5

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include <cmath>
#include <math.h>
#include <algorithm>
#include <map>
#include <vector>
#include <utility>
#include <set>
#include <string>
#include <cstring>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <cassert>
#include <functional>
//#include <intrin.h>
#include <stack>
#include <thread>
using namespace std;
//typedef long long ll;
#define ll long long
#define ld long double

const long long mod = 1000000007;

#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)>(y)?(x):(y))
#define PI 3.14159265358979323846
#define ABS(a) ((a)<0?-(a):(a))
template <typename T> inline T gcd(T a, T b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}
long long fastpow(long long a, long long n)
{
    auto mult = a;
    long long res = 1;
    while (n)
    {
        if (n & 1)
            res *= mult;
        mult *= mult;
        n >>= 1;
    }
    return res;
}

long long GetTortHareRes(long long mod, long long mult, long long x)
{
    long long tortoise = 1, hare = 1, tail = 1, loop = 1;
    tortoise = (tortoise * mult) % mod;
    hare = (hare * mult) % mod;
    hare = (hare * mult) % mod;
    while (hare != tortoise)
    {
        tortoise = (tortoise * mult) % mod;
        hare = (hare * mult) % mod;
        hare = (hare * mult) % mod;
        tail++;
    }
    tortoise = (tortoise * mult) % mod;
    while (hare != tortoise)
    {
        tortoise = (tortoise * mult) % mod;
        loop++;
    }
    x = x < tail ? x : tail + (x - tail) % loop;
    long long ans = 1;
    for (long long i = 0; i < x; i++)
        ans = (ans * mult) % mod;
    return ans;
}

long long CountLimitedPairs(long long maxdif, vector<long long>& sorted)
{
    long long ans = 0;
    int l = 0, r = 0;
    while (r < sorted.size())
    {
        while (sorted[r] - sorted[l] <= maxdif)
        {
            ans += r - l;
            r++;
        }
        l++;
    }
    return ans;
}

void GetDivs(long long a, vector<long long>& divs)
{
    divs.clear();
    for (long long i = 2; i * i <= a; i++)
    {
        while (a % i == 0)
        {
            a /= i;
            divs.push_back(i);
        }
    }
    if (a != 1)
    {
        divs.push_back(a);
    }
}

void Eratosfen(int n, vector<bool>& res)
{
    res.clear();
    res.resize(n, 1);
    for (int i = 2; i * i <= n; i++)
    {
        if (res[i - 1])
        {
            for (int j = i * i; j <= n; j += i)
            {
                res[j] = 0;
            }
        }
    }
}

long long fPow(long long a, long long b, long long mod)
{
    long long ans = 1;
    long long mn = a;
    while (b)
    {
        if (b & 1)
        {
            ans *= mn;
            ans %= mod;
        }
        mn *= mn;
        mn %= mod;
        b >>= 1;
    }
    return ans;
}

long long gcd(long long a, long long b)
{
    return b ? gcd(b, a % b) : a;
}

long long gcd(long long a, long long b)
{
    while (b)
    {
        a = a % b;
        swap(a, b);
    }
    return a;
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    return 0;
}