bzoj 1406

%%% PoPoQQQ

 x^2=kn+1

x^2-1=kn

(x+1)(x-1)=kn

令x+1=k1*n1,x-1=k2*n2，其中k1k2=k,n1n2=n

因此我们可以枚举n的约数中所有大于等于$sqrt{n}$的，分别作为n1和n2代入验证.

这么水的题我竟然没想出来TAT

复杂度$sum_{d|n&&d<=sqrt n}d$

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#define N 500005
using namespace std;
int ans[N],top;
set<int>s;
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            int t=n/i;
            for(int j=0;j<=n;j+=t)
            {    
                if((j+2)%i==0)s.insert(j+1);
                if(j>=2&&(j-2)%i==0)s.insert(j-1);
            }
        }
    }
    if(!s.size())puts("None
");
    set<int>::iterator i;  
    for (i=s.begin();i!=s.end();i++)if(*i<n)printf("%d
",*i);  
    return 0;
}