打表或者画个图可以看出i>根号n时每个i的贡献值相差很小，可以利用公式优化（函数C） 但是注意不能一整段使用公式，否则复杂度还是会劣化到O(n)（显然对gongxian只能逐步递减） 网上看了不少代码，但是都没有对贡献值边界问题给定明确的判断 所以还是加多一个while循环确定贡献值的开端是前面的n/i没有的
1#include<bits/stdc++.h> 2using namespace std; 3const int maxn = 1e5+11; 4typedef long long ll; 5ll H(ll n,ll j){ 6 ll ans=0; 7 for(int i = 1; i <= j; i++) ans+=n/i; 8 return ans; 9} 10ll C(ll n,ll gongxian){ 11 return gongxian*(n/gongxian-n/(gongxian+1)); 12} 13int main(){ 14 int T,kase=0; scanf("%d",&T); 15 while(T--){ 16 ll n; scanf("%lld",&n); 17 if(n<=20){ 18 printf("Case %d: %lld\n",++kase,H(n,n)); 19 continue; 20 } 21 ll gen = sqrt(n); 22 ll ans1 = H(n,gen); 23 ll tmp = n/gen; 24 ll cnt=gen; 25 while(1){ 26 if(n/gen==n/(cnt+1)){ 27 ans1+=n/gen; 28 cnt++; 29 } 30 else{ 31 cnt++;//start 32 break; 33 } 34 } 35 ll gongxian = n/cnt; 36 ll ans2=0; 37 while(gongxian){ 38 ans2+=C(n,gongxian); 39 gongxian--; 40 } 41 printf("Case %d: %lld\n",++kase,ans1+ans2); 42 } 43 return 0; 44}
顺便附加对规律观察用的代码
1#include<bits/stdc++.h> 2#define rep(i,j,k) for(int i = j; i <= k; i++) 3#define scan(a) scanf("%d",&a) 4using namespace std; 5typedef pair<int,int> P; 6const int maxn = 1e6+11; 7typedef long long ll; 8int cnt[maxn],n; 9bool C(int n){ 10 memset(cnt,0,sizeof cnt); 11 rep(i,1,n) cnt[n/i]++; 12 int maxzero=0,num=0; 13 rep(i,1,n) if(i>=sqrt(n)&&cnt[i]==1) num++; 14 // cout<<(int)sqrt(n+0.5)+1<<" "<<cnt[(int)sqrt(n+0.5)+1]<<endl; 15 // return cnt[(int)sqrt(n+0.5)+1]; 16 cout<<num<<endl; 17} 18int main(){ 19 // rep(i,1,10000) if(C(i)) cout<<i<<endl; 20 srand(time(NULL)); 21 int n=rand()%1000000; 22 C(n);cout<<sqrt(n)<<endl; 23}
可以看出[根号n,n]对答案的贡献基本等于根号n
1#include<bits/stdc++.h> 2using namespace std; 3int main(){ 4 int cnt=0; 5 for(int i = 100; i <= 1e6; i++){ 6 int a=i/(int)sqrt(i),b=sqrt(i); 7 if(a-b<0) cnt++; 8 // cout<<i<<" "<<a-b<<endl; 9 10 } 11 cout<<cnt<<endl; 12}
可以看出a（应该）都是大于等于b 待做同类题目:1257 2956
1//BACKUP 2#include<bits/stdc++.h> 3using namespace std; 4const int maxn = 1e5+11; 5typedef long long ll; 6ll cal(int n,int k){ 7 ll ans=0; 8 for(int i = 1; i <= n; i++) ans+=k%i;//k-(k/i)*i 9 return ans; 10} 11ll G(int n,int k){ 12 ll ans=0; 13 for(int i = 1; i <= n; i++) ans+=(k/i)*i; 14 return ans; 15} 16ll con(ll k,ll i){return i*(k/i-k/(i+1));} 17ll sum(ll a1,ll n,ll d){return a1+(n-1)*d;} 18int main(){ 19 int n,k; 20 while(cin>>n>>k){ 21 if(n<=100){ 22 cout<<cal(n,k)<<endl; 23 continue; 24 } 25 ll root=sqrt(n); 26// cout<<"root"<<root<<endl; 27 ll ans1=1ll*k*n; 28 ll ans2=G(root,k); // 29 ll ans3=0; 30 int cnt=root+1; 31 32 if(k/cnt==0){//防止越界处理 33 cout<<ans1-G(root,k)<<endl; 34 continue; 35 } 36 while(1){ 37 if(k/root==k/(cnt+1)){ 38 ans3+=(k/(cnt+1))*(cnt+1); 39 cnt++; 40// cout<<k/root<<" "<<k/cnt<<endl; 41 } 42 else{ 43 cnt++; 44 break; 45 } 46 } 47 bool flag=0; 48 ll lim=k/n; if(lim==0) lim++; 49 ll val=k/cnt; if(val==0) flag=1; 50 ll now=cnt; 51 ll ans4=0; 52 while(!flag&&val>=lim){ 53 cout<<"NOW "<<now<<endl; 54 ll LEN = k/val-k/(val+1); 55 cout<<"LEN "<<LEN<<endl; 56 cout<<"VAL "<<val<<endl; 57 ans4+=con(k,val)*(LEN?sum(now,LEN,1):0); 58 now+=LEN; 59 val--; 60 } 61 cout<<ans1-(ans2-ans3-ans4)<<endl; 62 } 63 return 0; 64}