打表或者画个图可以看出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;
}