BZOJ1406:[AHOI2007]密码箱 数学+暴力
思路:
令x是一个可行答案,有x2%n=1,即(x−1)(x+1)=kn(k∈Z).
显然我们可以令x−1=k1n1,x+1=k2n2,k=k1k2,n=n1n2.(交换一下也是可以的)
那么我们就可以枚举所有的n1,看一看他能够表达出的x+1或是x−1是不是一个合法答案.我们用一个哈希表来支持插入.最后输出即可.
但是我们发现枚举所有的n1(n的约数)显然是要超时的.因此我们只枚举n1≥√n的n1.这样单次枚举的复杂度为√n,而且这样的约数非常少,这样就可以通过了.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #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;} |
评论 (0)