BZOJ 1406 密码箱

       大致看一下题目可以发现题目相当简单，似乎一个暴力就OK，但是一看数据范围没戏了，仔细进行一下分析发现这是一道数学题。题目的意思是：A²=kn+1，将之简单整理一下可以得到A²-1=kn，（A+1）*（A-1）=kn，这样看来由于A是整数，所以我们只需对kn进行因数分解，之后相信大家都知道了。

程序如下：

#include<iostream>
#include<cstdlib> 
#include<cstdio>
#include<set>
#include<cmath>
 
using namespace std;
 
set<int> ans;
 
int main()
{
    int n;
    scanf("%d", &n);
   
    if(n > 1) ans.insert(1);
    int m = (int)(sqrt(n) + 0.5);
    for(int i = 1; i <= m; i++) if(n % i == 0)
    {
        int j = n / i;
        for(int k = j; k <= n; k+=j)
        {
            if((k-2) % i == 0)  ans.insert(k-1);
            if((k+2) % i == 0)  ans.insert(k+1);
        }
    }
    for(set<int>::iterator it = ans.begin(); it != ans.end(); it++)
    {
        if((*it) < n) printf("%d
", *it);
    }
    
    return 0;
}