BZOJ1406:[AHOI2007]密码箱 数学+暴力

思路:

令\(x\)是一个可行答案,有\(x^2\%n=1\),即\((x-1)(x+1)=kn(k\in{Z})\).

显然我们可以令\(x-1=k_1n_1,x+1=k_2n_2,k=k_1k_2,n=n_1n_2\).(交换一下也是可以的)

那么我们就可以枚举所有的\(n_1\),看一看他能够表达出的\(x+1\)或是\(x-1\)是不是一个合法答案.我们用一个哈希表来支持插入.最后输出即可.

但是我们发现枚举所有的\(n_1\)(n的约数)显然是要超时的.因此我们只枚举\(n_1\geq{\sqrt{n}}\)的\(n_1\).这样单次枚举的复杂度为\(\sqrt{n}\),而且这样的约数非常少,这样就可以通过了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
static const int mod=(1e5)+7;
struct HashSet{
    int head[mod],v[200010],next[200010],ind;
    void reset(){ind=0,memset(head,-1,sizeof head);}
    void insert(int x){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])if(v[j]==x)return;
        v[ind]=x,next[ind]=head[ins],head[ins]=ind++;
    }
}S;
 
int n;
void Solve(int x){
    for(int d=x;d<n-1;d+=x)if((long long)d*(d+2)%n==0)S.insert(d+1);
    for(int d=x;d<=n;d+=x)if(d-2>=1&&(long long)d*(d-2)%n==0)S.insert(d-1);
}
int main(){
    scanf("%d",&n);
    if(n==1)puts("NONE");
    else{
        S.reset(),S.insert(1);
        for(int i=1;i*i<=n;++i)if(n%i==0)Solve(max(i,n/i));
        sort(S.v,S.v+S.ind);
        for(int i=0;i<S.ind;++i)printf("%d\n",S.v[i]);
    }
     
    return 0;
}