内存极限AC

#include<bits/stdc++.h>
//#define int long long
//千万不要加，不然就会MLE 
using namespace std;
constexpr int N=1e6+10;
int n,Q;//Q表示k和Q 
long long s[N];//前缀和数组 
unordered_map<int,int>mp;//表示该数在x_i中出现的次数（核心）
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>Q;
	while(Q--){
		int x;
		cin>>x;
		mp[x]++;//首先进行记录 
	}
	for(int i=0;i<n;i++)if(mp[i])//如果该数出现过（如果不判定就会TLE）
		for(int j=0;j<n;j+=i)//执行something函数 
			s[j]+=mp[i];//这样就可以一次执行多次的重复任务，减少时间复杂度 
	for(int i=1;i<n;i++)
		s[i]+=s[i-1];//前缀和 
	cin>>Q;
	while(Q--){
		int l,r;
		cin>>l>>r;
		if(l==0)cout<<s[r]<<"\n";//在这个世界中，没有第-1个下标！！！ 
		else cout<<s[r]-s[l-1]<<"\n";
	}
	return 0;
}//该程序时间复杂度为O(n/1+n/2+n/3+...+n/n)=O(nlogn) 

读完题可以发现,这题考的是时间复杂度优化.所以我就讲一下这个时间复杂度是怎么推出来的.

第一步

首先就是纯暴力$O(K(N/Xi)+N^2)$:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,q,a[1000010],s[1000010],cnt[1000010];
int main()
{
	scanf("%lld%lld",&n,&k);
	for(ll i=1;i<=k;i++)scanf("%lld",&a[i]);
	for(ll i=1;i<=k;i++)for(ll j=0;j<n;j+=a[i])s[j]++;
	scanf("%lld",&q);
	for(ll i=1,x,y;i<=q;i++)
	{
		scanf("%lld%lld",&x,&y);
		ll ans=0;
		for(ll j=x;j<=y;j++)ans+=s[j];
		printf("%lld\n",ans);
	}
	return 0;
}

然后就会得到60分......

第二步

然后我们可以想到用前缀和来优化掉一层. 就会有这个代码$O(K(N/Xi))$(优化后的那一层$O(N)$可以忽略不计):

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,q,a[1000010],s[1000010];
int main()
{
	scanf("%lld%lld",&n,&k);
	for(ll i=1;i<=k;i++)scanf("%lld",&a[i]);
	for(ll i=1;i<=k;i++)for(ll j=0;j<n;j+=a[i])s[j]++;
	for(ll i=1;i<=n;i++)s[i]+=s[i-1];
	scanf("%lld",&q);
	for(ll i=1,x,y;i<=q;i++)
	{
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",s[y]-s[x-1]);
	}
	return 0;
}

然后就会有90分......

第三步

然后我们就会发现:时间就差一点...(58ms)

所以尝试把最后的一层优化掉一点就可以了... 那$O(K(N/Xi))$(k与n取值范围相同)的下一层是什么呢?

没错!就是$O(NlogN)$,想到这里,就可以想到约数个数性质,就能构造出正解了.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,q,s[1000010],cnt[1000010];
int main()
{
	scanf("%lld%lld",&n,&k);
	for(ll i=1,x;i<=k;i++)scanf("%lld",&x),cnt[x]++;
	for(ll i=0;i<n;i++)if(cnt[i])
	{
		for(ll j=0;j<n;j+=i)s[j]+=cnt[i];
	}
	for(ll i=1;i<n;i++)s[i]+=s[i-1];
	scanf("%lld",&q);
	for(ll i=1,x,y;i<=q;i++)
	{
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",s[y]-s[x-1]);
	}
	return 0;
}

然后就能AC了

#include<bits/stdc++.h>
using namespace std;
#define re register
const int N=1e6+10;
int mx,cnt[N];long long seq[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,k;cin>>n>>k;
	for(re int i=1,x;i<=k;i++)
		cin>>x,cnt[x]++,mx=max(mx,x);
	for(re int i=1;i<=mx;i++)if(cnt[i])
		for(re int j=0;j<n;j+=i)seq[j]+=cnt[i];
	for(re int i=1;i<n;i++)seq[i]+=seq[i-1];
	int q;cin>>q;
	for(re int i=1,l,r;i<=q;i++)
	{
		cin>>l>>r;
		cout<<seq[r]-seq[l-1]<<'\n';
	}
	return 0;
}

很容易想到一种暴力：统计每种 jump 的出现次数 cnt[jump]，然后

for (int jump = 1; jump <= N; ++jump)
  for (int i = 0; i < N; i += jump)
    seq[i] += cnt[jump];

你以为这东西的时间复杂度是 $O(N^2)$ 的，结果……你发现这个程序居然 AC 了。

原因很简单，还记得约数个数性质吗？

$O(N+\frac N 2+\frac N 3+\dots+\frac N N)=O(N\log N)$

最后吐槽一句，尽管这个题考点很正常，但个人觉得这题丢到考场上是会搞出负区分度的（