C++14(g++5.4) 解法, 执行用时: 181ms, 内存消耗: 12624K, 提交时间: 2018-08-31 19:08:45

#include<bits/stdc++.h>
using namespace std;
int sg[100100],vis[100100],pre[100100],suf[100100],a[100100];
vector<int>G[100100]; 
int main(){
	sg[0]=0;
	int M=1e5;
	for(int i=1;i<=M;++i)
		for(int j=i;j<=M;j+=i)
			G[j].push_back(i);
	for(int i=1;i<=M;++i){
		for(auto c:G[i])vis[sg[i-c]]=i;
		for(sg[i]=0;vis[sg[i]]==i;sg[i]++);
	}
	int n,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)pre[i]=pre[i-1]^sg[a[i]];
	for(int i=n;i>=1;--i)suf[i]=suf[i+1]^sg[a[i]];
	for(int i=1;i<=n;++i){
		int xr=pre[i-1]^suf[i+1];
		for(auto c:G[a[i]])if(xr==sg[a[i]-c])ans++;
	}
	printf("%d",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 146ms, 内存消耗: 11584K, 提交时间: 2018-08-31 19:22:47

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
int n,m,i,j,s[MAXN],a[MAXN],ans;
vector<int> d[MAXN];
bool b[MAXN];
int main()
{
	n=100000;
	for(i=1;i<=n;i++)for(j=1;i*j<=n;j++)d[i*j].push_back(i);
	for(i=1;i<=n;i++)
	{
		m=d[i].size();
		for(j=0;j<m;j++)b[s[i-d[i][j]]]=1;
		for(s[i]=0;;s[i]++)if(!b[s[i]])break;
		for(j=0;j<m;j++)b[s[i-d[i][j]]]=0;
	}
	scanf("%d",&n);
	for(i=1,m=0;i<=n;i++)
	{
		scanf("%d",a+i);
		m^=s[a[i]];
	}
	for(i=1;i<=n;i++)for(j=0;j<d[a[i]].size();j++)if(s[a[i]-d[a[i]][j]]==(m^s[a[i]]))ans++;
	cout<<ans<<endl;
	return 0;
}