CF1263C Everyone is a Winner!

整数分块的入门题。

求取n/k向下取整可以得到的值。

12:1∼1,6:2∼2,4:3∼3,3:4∼4,2:5∼6,1:7∼12,0:k≥13

通过枚举我们发现，有很多的区块拥有相同的区块值。

设区块左右端点为l,r，则有区块值value=n/l。

同时我们发现r=n/value，且下一个区块的l=当前r+1。

所以我们可以通过该区块的l跳到下一个区块的l，也就是说我们可以O1枚举每个区间，而不用经过l到r之间的数。

这样算法的时间复杂度从O(n)优化到了O(sqrt(n))。

该题ac代码

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

int n;

void dfs(LL l,int cnt){
    if(l>n){
        cout<<cnt+1<<endl;
        cout<<0<<' ';
        return;
    }
    LL r=n/(n/l);
    dfs(r+1,cnt+1);
    cout<<n/l<<' ';
}

void solve(){
    cin>>n;
    //为了符合顺序采用了递归
    dfs(1,0);
    cout<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

JZTXT

整数分块

CF1263C Everyone is a Winner!