二分

0求阶乘 - 蓝桥云课 (lanqiao.cn)

只有5 * 2 才能=10 才可能出现0 由于2 必定比5多 只需要求5 的个数

二分法求到mid的时候前面有多少5 不断除以5就可以算出来

#include <iostream>
using namespace std;
typedef long long ll;
ll x;
ll check(ll mid)
{
    ll ret = 0;
    while (mid > 0)
    {
        ret += mid / 5;
        mid /= 5;
    }
    return ret;
}

int main()
{
    
    cin>>x;
    ll l = 1, r = 6e18;
    ll res = -1;
    while (l < r)
    {
        ll mid = l + r >> 1;
        ll s = check(mid);
        if (s < x)
            l = mid + 1;
        else
            r = mid;
    }
    if (check(r) == x)
    cout<<r;
    else cout<<-1;
}

1236. 递增三元组 - AcWing题库

找这个三元组 主要是看中间一行 比如

A 1 4 5
B 5 6 9
C 4 6 7

就看B的5能和A结合几个 能和C结合几个

1 4 
5 
  6 7  

结果为2 * 2 = 4

所以只需要对B的每一个数在A C两个数组内进行二分 求出比他小的第一个数 和比他大的第一个数即可

然后注意一些下标的处理

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int nums[3][N];
int main()
{
    int n;
    cin>>n;
    
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin>>nums[i][j];
        }
        sort(nums[i], nums[i] + n);
    }
    
    long long res = 0;
    for (int i = 0; i < n; i++)
    {
        int key = nums[1][i];
        int pos1 = lower_bound(nums[0], nums[0] + n, key) - nums[0]; // 在A中找到第一个小于key的数
        int pos2 = upper_bound(nums[2], nums[2] + n, key) - nums[2] + 1; // 在C中找到第一个大于key的数
        
        res += (long long)(n - pos2 + 1) * pos1;
    }
    cout<<res;
}