观察数学关系找到突破口

题目传送门

大致思路

已知 $q=[\frac{x}{y}]$ 和 $r=x\%y$

$$q=\frac{x-r}{y} $$

$$x=qy+r $$

$x$ 有上限 $k$ , $y$越小,对于该 $q$ 能取到的 $r$ 越大
那么就让 $y=r+1$ 取到最小
对于所有 $q$ 二分得到能取到的最大 $r$ ,然后在 $r$ 集合中二分找到小于等于这个最大的 $r$ 的最大值,将其与该 $q$ 组合,即删去

Code

void solve() {
    int n,k;
    cin >> n >> k;
    vector<int> q;
    multiset<int> r;
    for (int i=0;i<n;i++) {
        int x;
        cin >> x;
        q.pb(x);
    }
    for (int i=0;i<n;i++) {
        int x;
        cin >> x;
        r.insert(x);
    }
    int ans=0;
    for (int i=0;i<n;i++) {
        if (q[i]>k) continue;
        int left=0,right=1e9,res=-1;
        while (left<=right) {
            int mid=left+(right-left)/2;
            int t=mid+q[i]*(mid+1);
            if (t<=k) {
                res=mid;
                left=mid+1;
            }
            else right=mid-1;
        }
        if (res!=-1) {
            auto it=r.upper_bound(res);
            if (it!=r.begin()) {
                it--;
                r.erase(it);
                ans++;
            }
        }
    }
    cout <<ans<<el;
}

题目传送门

大致思路

求$[\frac{N}{M}]$(mod 10007) , 有 $((N\%10007-N\%M))\%10007*inv\_m$(mod 10007)

新加入一段长度 $l$ ,数字为 $c$ 的段,那么$N=(N*10^{l}+(10^{l}-1)/9*c)$
但是 $9$ 不是质数,不能求逆元,那么直接求一段全为 $c$ 长度为 $l$ 的数字加到 $N$ 中

直接求 $S(l)=1+10^{1}+10^{2}....+10^{l-1}$会超时,考虑利用快速幂中类似方法求取:
当前 $l$ 为偶数,则 $S(l)=S(l/2)*(1+10^{l/2})$
当前 $l$ 为奇数,则 $S(l)=S(l-1)*10+c$
递归求得

Code

int fastpow(int base, int exp,int mod) {
    int result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (base*result)%mod;
        exp >>= 1;
        base = (base*base)%mod;
    }
    return result;
}

int inv(int a,int mod) {
    return fastpow(a,mod-2,mod);
}

void solve() {
    int k,m;
    cin >> k >> m;
    int cur1=0,cur2=0;
    auto bzd=[&](auto && self,int l,int c,int mod)->int {
        if (l==1) return c%mod;
        if (l&1) return (self(self,l-1,c,mod)*10+c)%mod;
        int t=self(self,l/2,c,mod);
        return (t*(1+fastpow(10,l/2,mod)))%mod;
    };
    for (int i=1;i<=k;i++) {
        int c,l;
        cin >> c >> l;
        cur1=(cur1*fastpow(10,l,10007))%10007;
        cur2=(cur2*fastpow(10,l,m))%m;
        cur1=(cur1+bzd(bzd,l,c,10007))%10007;
        cur2=(cur2+bzd(bzd,l,c,m))%m;
    }
    int ans=(((cur1-cur2)+10007)%10007)*inv(m,10007);
    ans%=10007;
    cout << ans<<el;
}