打表或者画个图可以看出i>根号n时每个i的贡献值相差很小，可以利用公式优化（函数C） 但是注意不能一整段使用公式，否则复杂度还是会劣化到O(n)（显然对gongxian只能逐步递减） 网上看了不少代码，但是都没有对贡献值边界问题给定明确的判断 所以还是加多一个while循环确定贡献值的开端是前面的n/i没有的

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+11;
typedef long long ll;
ll H(ll n,ll j){
    ll ans=0;
    for(int i = 1; i <= j; i++) ans+=n/i;
    return ans;
}
ll C(ll n,ll gongxian){
    return gongxian*(n/gongxian-n/(gongxian+1));
}
int main(){
    int T,kase=0; scanf("%d",&T);
    while(T--){
        ll n; scanf("%lld",&n);
        if(n<=20){
            printf("Case %d: %lld\n",++kase,H(n,n));
            continue;
        }
        ll gen = sqrt(n);
        ll ans1 = H(n,gen);
        ll tmp = n/gen;
        ll cnt=gen;
        while(1){
            if(n/gen==n/(cnt+1)){
                ans1+=n/gen;
                cnt++;
            }
            else{
                cnt++;//start
                break;
            }
        }
        ll gongxian = n/cnt;
        ll ans2=0;
        while(gongxian){
            ans2+=C(n,gongxian);
            gongxian--;
        }
        printf("Case %d: %lld\n",++kase,ans1+ans2);
    }
    return 0;
}

顺便附加对规律观察用的代码

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i = j; i <= k; i++)
#define scan(a) scanf("%d",&a)
using namespace std;
typedef pair<int,int> P;
const int maxn = 1e6+11;
typedef long long ll;
int cnt[maxn],n;
bool C(int n){
    memset(cnt,0,sizeof cnt);
    rep(i,1,n) cnt[n/i]++;
    int maxzero=0,num=0;
    rep(i,1,n) if(i>=sqrt(n)&&cnt[i]==1) num++;
    // cout<<(int)sqrt(n+0.5)+1<<" "<<cnt[(int)sqrt(n+0.5)+1]<<endl;
    // return cnt[(int)sqrt(n+0.5)+1];
    cout<<num<<endl;
}
int main(){
    // rep(i,1,10000) if(C(i)) cout<<i<<endl;
    srand(time(NULL));
    int n=rand()%1000000;
    C(n);cout<<sqrt(n)<<endl;
}

可以看出[根号n,n]对答案的贡献基本等于根号n

#include<bits/stdc++.h>
using namespace std;
int main(){
    int cnt=0;
    for(int i = 100; i <= 1e6; i++){
        int a=i/(int)sqrt(i),b=sqrt(i);
        if(a-b<0) cnt++;
        // cout<<i<<" "<<a-b<<endl;
        
    }
    cout<<cnt<<endl;
}

可以看出a（应该）都是大于等于b 待做同类题目:1257 2956

//BACKUP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+11;
typedef long long ll;
ll cal(int n,int k){
    ll ans=0;
    for(int i = 1; i <= n; i++) ans+=k%i;//k-(k/i)*i
    return ans; 
}
ll G(int n,int k){
    ll ans=0;
    for(int i = 1; i <= n; i++) ans+=(k/i)*i;
    return ans; 
}
ll con(ll k,ll i){return i*(k/i-k/(i+1));}
ll sum(ll a1,ll n,ll d){return a1+(n-1)*d;}
int main(){
    int n,k;
    while(cin>>n>>k){
        if(n<=100){
            cout<<cal(n,k)<<endl;
            continue;
        }
        ll root=sqrt(n);
//        cout<<"root"<<root<<endl;
        ll ans1=1ll*k*n;
        ll ans2=G(root,k); //
        ll ans3=0;
        int cnt=root+1;
        
        if(k/cnt==0){//防止越界处理 
            cout<<ans1-G(root,k)<<endl;
            continue;
        }
        while(1){
            if(k/root==k/(cnt+1)){
                ans3+=(k/(cnt+1))*(cnt+1);
                cnt++;
//                cout<<k/root<<" "<<k/cnt<<endl;
            }
            else{
                cnt++;
                break;
            }
        }
        bool flag=0;
        ll lim=k/n; if(lim==0) lim++; 
        ll val=k/cnt; if(val==0) flag=1;
        ll now=cnt;
        ll ans4=0;
        while(!flag&&val>=lim){
            cout<<"NOW "<<now<<endl;
            ll LEN = k/val-k/(val+1);
            cout<<"LEN "<<LEN<<endl;
            cout<<"VAL "<<val<<endl;
            ans4+=con(k,val)*(LEN?sum(now,LEN,1):0);
            now+=LEN;
            val--;
        }
        cout<<ans1-(ans2-ans3-ans4)<<endl;
    }
    return 0;
}