Codeforces Round#701 C.Floor and Mod数学の導出

Codeforces Round#701 C.Floor and Mod数学の導出

題意

構想

Code(62MS)

転送ゲート:https://codeforces.com/contest/1485/problem/C
に言及
xとyを与えて、⌊a b⌋=axとyをあげて、leftlfloorfrac{a}{b}rightrfloor=a;を求めます;mod\;b成立の個数.xとyをあげて、⌊ba⌋=amodbが成立する個数を求めます.1 ≤ a ≤ x        1 ≤ b ≤ y 1\leq a\leq x\;\;\;1\leq b\leq y 1≤a≤x1≤b≤y
構想
明らかにこの問題は明らかにこの問題はleftlfloorfrac{a}{b}rightrfloor=a;をめぐっている.mod\;b.明らかにこの問題は制限がなければb−1個(0は存在しない)がある.制限がなければred{b−1}個(0は存在しない)がある.制限がなければb−1個(0は存在しない)がある.
私たちは3 2、4 3を手で出すことができます.そして、8 3もできます.私たちはfrac{3}{2},frac{4}{3}を手で出すことができ、frac{8}{3}もできます.23、34を手で出してもいいし、38でもいいです.従って、b+1 b=1、2(b+1)b=2等である.だからfrac{b+1}{b}=1,frac{2(b+1)}{b}=2など.したがってbb+1=1,b 2(b+1)=2などである.
k(b+1)b=k=ak(b+1)≦aだから私たちはfrac{k(b+1)}{b}=k=a;mod\;b.red{k(b+1)leq a}だからbk(b+1)=k=amodbを得なければなりません.k(b+1)≤a
bを列挙するが,テーマには制限条件があり,m i nを取ればよい.bを列挙しますが、テーマには制限条件があります.minを取ればいいです.bを列挙しますが、テーマには制限条件があります.minを取ればいいです.
∑ i = 2 b m i n ( i − 1 , a i + 1 )\sum_{i=2}^bmin(i-1,\frac{a}{i+1}) i=2∑b​min(i−1,i+1a​)
まず中間値i−1=a i+1,i=a+1を計算し,最後に,まず中間値i−1=frac{a}{i+1},i=sqrt{a+1}を計算し,最後に,まず中間値i−1=i+1 a,i=a+1を計算し,最後に:
∑ i = 2 a + 1 i − 1 + ∑ i = a + 1 + 1 b a i + 1\sum_{i=2}^{\sqrt{a+1}}i-1+\sum_{i=\sqrt{a+1}+1}^b\frac{a}{i+1} i=2∑a+1 ​​i−1+i=a+1 ​+1∑b​i+1a​
前半は等差数列で和を求め、後半はブロックを除去すればよい.前半は等差数列で和を求め、後半はブロックを除去すればよい.前半は等差数列で和を求め、後半はブロックを除去すればよい.
Code(62MS)

#include "bits/stdc++.h"
 using namespace std;
 
typedef long long ll;
 
 
void solve() {
     
 
    int _; cin >> _;
    while(_--) {
     
        ll a, b; cin >> a >> b;
        ll ans = 0;
        ll t = sqrt(a + 1);
        if(t > b) {
     
            t = b;
            ans += t * (t - 1) / 2;
        }
        else {
     
            ans += t * (t - 1) / 2;
            for (ll l = t + 1, r; l <= min(a, b); l = r + 1) {
     
                if (a / (l + 1) == 0) break;
                else r = min(b, min(a, a / (a / (l + 1)) - 1));
                ans += (r - l + 1) * (a / (l + 1));
            }
        }
        cout << ans << endl;
    }
}
 
signed main() {
     
    solve();
}