題目

X*X mod P = A，其中P為質(zhì)數(shù)。給出P和A，求<=P的所有X。

輸入

兩個數(shù)P A，中間用空格隔開。(1 <= A < P <= 1000000, P為質(zhì)數(shù))

輸出

輸出符合條件的X，且0 <= X <= P，如果有多個，按照升序排列，中間用空格隔開。
如果沒有符合條件的X，輸出：No Solution

輸入樣例

13 3

輸出樣例

4 9

思路：

由于給定 p 和 a，假設(shè) x 存在，那么 x 的個數(shù)為 2 個，即：x1、x2

由于 x1*x1-x2*x2=n*p，那么：x1+x2=p，即 x1、x2 互補

考慮 a 是否完全平方數(shù)即可，當 a 不為完全平方數(shù)時，那么就可以排除 0~p 取整后的數(shù)據(jù)

因此需要枚舉（p 的開方數(shù)取整后+1）~（p/2 取整）

故暴力即可

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define E 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD=7; const int N=1000000+5; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std; LL a[N]; int main(){LL p,a;scanf("%lld%lld",&p,&a);int i=0;bool flag=true;while(true){double x1=sqrt(i*p*1.0+a*1.0);int x2=(int)x1;if(x2>p)break;if(x1==x2){printf("%d ",x2);flag=false;}i++;}if(flag)printf("No Solution");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的X^2 Mod P（51Nod-1014）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。