```cpp
#include<bits/stdc++.h>
#define pb push_back
#define forup(i,a,b) for(int i=(a);i<=(b);i++)
#define fordown(i,a,b) for(int i=(a);i>=(b);i--)
#define maxn 1000005
#define N 131073
#define INF 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline void read(T& num){ num = 0; bool f = true;char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = false;ch = getchar();} while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();} num = f ? num: -num; }
int out[100];
template<class T> inline
void write(T x,char ch){ if (x==0) {putchar('0'); putchar(ch); return;} if (x<0) {putchar('-'); x=-x;} int num=0; while (x){ out[num++]=(x%10); x=x/10;} fordown(i,num-1,0) putchar(out[i]+'0'); putchar(ch); }
/*========================================================*/
int n,K;
int a[maxn];
int dp[maxn];
bool vis[maxn];
int cnt;
int ans[maxn];
bool check(int x)
{ bool flag=1;
for (int k = 1; k * k - a[x] < N; k++)
{ if (k * k - a[x] <= 0) continue;
if (vis[k * k - a[x]]) {flag = 0;break;}
}
return flag;
}
void cheat1()
{ int r=n,l=n;
while(r)
{ while(l)
{if(check(l)) {vis[a[l]]=1;l--;}
else break;
}
if (!l) break;
ans[++cnt] = l;
for ( ; r > l; r--) vis[a[r]] = 0;
}
write(cnt+1,'\n');
fordown(i,cnt,1) write(ans[i],' ');
}
vector<int> g[maxn];
bool sqr[maxn];
int col[maxn];
bool dfs(int x,int f)
{ col[x]=f;
bool flag=1;
for(int i=0;i<g[x].size();i++)
{int u=g[x][i];
if(col[x]==col[u]) {flag=0;break;}
if(col[u]==-1) flag=flag&dfs(u,f^1);
}
return flag;
}
bool check2(int l,int r)
{//cout<<"case"<<endl;
//cout<<l<<' '<<r<<endl;
bool flag=1;
forup(i,l,r)
forup(j,i+1,r)
{//cout<<i<<' '<<j<<endl;
if(sqr[a[i]+a[j]]) g[i].pb(j),g[j].pb(i);
}
forup(i,l,r) col[i]=-1;
forup(i,l,r) if(col[i]==-1) {if(dfs(i,0)==0) {flag=0;break;}}
forup(i,l,r) g[i].clear();
return flag;
}
void cheat2()
{ int r=n,l=n;
while(r)
{ while(l)
{if(check2(l,r)) {l--;}
else break;
}
if (!l) break;
ans[++cnt] = l;
r=l;
}
write(cnt+1,'\n');
fordown(i,cnt,1) write(ans[i],' ');
}
int main()
{freopen("division2.in","r",stdin);
//freopen("1.out","w",stdout);
forup(i,1,1000) sqr[i*i]=1;
cin>>n>>K;
forup(i,1,n) read(a[i]);
if(K==1)
{ cheat1();}
if(K==2)
{ cheat2();}
return 0;
}
```
by zhouyihe @ 2017-11-09 19:45:40
28分（不用倍增会更低）
```cpp
#include<cstdio>
#include<cmath>
const int N=2e5+1;
int n,k,m;
int a[N],ans[N];
int check(int r,int len){
int l=r-len+1;
if(l<1) return 0;
for(int i=l;i<=r;i=-~i)
for(int j=i+1;j<=r;j=-~j){
int s=std::sqrt(a[i]+a[j]);
if(s*s==a[i]+a[j])
return 0;
}
return 1;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i=-~i)
scanf("%d",a+i);
while(n){
int s=0;
for(int i=20;i>=0;i--)
if(check(n,s+(1<<i)))
s+=1<<i;
n-=s;ans[++m]=n;
}
printf("%d\n",m);
for(int i=m-1;i>=1;i--)
printf("%d ",ans[i]);
return 0;
}
```
by anideahe @ 2022-01-18 16:09:33