正題

題目鏈接:https://www.luogu.com.cn/problem/P4296

---

題目大意

一個數字$n$，求有多少個$x<n$使得$x^2\%n=1$。

---

解題思路

$$x^2=kn+1$$
$$x^2?1=kn$$
$$(x?1)(x+1)\%n=0$$
$$?$$
$$x(x+2)\%n=0(x+2<=n)$$
對于這個式子，我們若有$ab=n(b>a)$，$a|x$且$b|y$的話那么就有$xy\%n=0$

所以我們可以先求出每一個$\ge \sqrt{n}$的$n$的約數$z$，然后這個約數是$a$還是$b$都行，然后暴力枚舉$z|x$的即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,p[100000],ans[200000],m,cnt; int main() {scanf("%d",&n);for(int i=1;i*i<=n;i++)if(!(n%i)) p[++m]=n/i;for(int i=1;i<=m;i++){int x=p[i];for(int j=x;j<=n;j+=x){if(!((j-2)%(n/x))) ans[++cnt]=j-1;if(!((j+2)%(n/x))) ans[++cnt]=j+1;}} sort(ans+1,ans+1+cnt);printf("1\n");for(int i=1;i<=cnt;i++)if(ans[i]!=ans[i-1]&&ans[i]<n)printf("%d\n",ans[i]); }

總結

以上是生活随笔為你收集整理的P4296-[AHOI2007]密码箱【数论】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。