【题解】 [AHOI2007]密码箱

数论。

题意：
给定一个正整数n，要求找到所有在[0,n)之间的整数x满足：%n=1。

思路：
%n=1可以写作=nk+1，即：(x-1)(x+1)=nk。拆分x与k得到：(x-1)(x+1)=(n1k1)(n2k2)，所以有：x-1=n1k1、x+1=n2k2。
接下来当n1<=n2时，可以在时间内枚举n1，同时计算出n2并枚举k2，计算出x，判断是否存在整数k1。
当n1>n2时同理枚举n2。此时要注意x<n的条件。

最后将两种情况的答案合并排序并去重后输出即可。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e4;//1e9+7;
const int maxn=1e5+9;
const ll maxx=1e12+9;

ll n;
vector<int> ans;

int main()
{
    scanf("%lld",&n);
    if(n>1) ans.push_back(1);
    ll m=sqrt(n+0.5);
    for(ll n1=1;n1<=m;n1++)
    {
        if(n%n1!=0) continue;
        ll n2=n/n1;
        for(ll k2=1;k2*n2<=n;k2++)
        {
            ll x=k2*n2-1;
            if((x-1)%n1==0) ans.push_back(x);
        }
    }
    for(ll n2=1;n2<=m;n2++)
    {
        if(n%n2!=0) continue;
        ll n1=n/n2;
        for(ll k1=1;k1*n1<n-1;k1++)
        {
            ll x=k1*n1+1;
            if((x+1)%n2==0) ans.push_back(x);
        }
    }
    sort(ans.begin(),ans.end());
    ans.resize(unique(ans.begin(),ans.end())-ans.begin());
    for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]);

}