2242: [SDOI2011]計算器 Time Limit: 10 Sec Memory Limit: 512 MB Description 你被要求設計一個計算器完成以下三項任務： 1、給定y,z,p,計算Y^Z Mod P 的值； 2、給定y,z,p，計算滿足xy≡ Z ( mod P )的最小非負整數； 3、給定y,z,p，計算滿足Y^x ≡ Z ( mod P)的最小非負整數。 Input 輸入包含多組數據。 第一行包含兩個正整數T,K分別表示數據組數和詢問類型（對于一個測試點內的所有數據，詢問類型相同）。 以下行每行包含三個正整數y,z,p，描述一個詢問。 Output 對于每個詢問，輸出一行答案。對于詢問類型2和3，如果不存在滿足條件的，則輸出“Orz, I cannot find x!”，注意逗號與“I”之間有一個空格。 Sample Input 【樣例輸入1】 3 1 2 1 3 2 2 3 2 3 3 【樣例輸入2】 3 2 2 1 3 2 2 3 2 3 3 【數據規模和約定】 對于100%的數據，1<=y,z,p<=10^9，為質數，1<=T<=10。 Sample Output 【樣例輸出1】 2 1 2 【樣例輸出2】 2 1 0 HINT Source 第一輪day1
/*復合題hhh.前兩問裸的快速冪 exgcd.讀入int64 不要圖快用scanf linux好像不行? 然后這題case 3 是BSGS.由于本人比較弱所以我只能感性的認識一下BSGS.y^x≡z(mod p).這題暴力的話復雜度是O(p)的.因為根據費馬小定理y^(p-1)≡1(mod p).剩余系元素的個數就是p-1,再往后就出現循環了.然后我們采用分塊的思想,令m=√p.然后就有y^(km+i)≡z(mod p).y^i≡ine(y^km)*z(mod p). (ine x為x的逆元).然后左邊hash存表,右邊枚舉k.然后因為費馬小定理有y^m*y^(p-m-1)≡1(mod p).so ine(y^m)=y^(p-m-1).右邊就變成了ine(y^m(k-x))*[ine(y^m)]^x.枚舉k即可. 復雜度就變成了O(sqrt(p)). */#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<map>#define LL long longusing namespace std;int k,t,n,p;LL a,b,x,y,c;map<int ,int >s;LL mi(){ LL tot=1; while(b) { if(b&1) tot=tot*a%p; a=a*a%p; b>>=1; } return tot%p;}void slove1(){ while(t--) { cin>>a>>b>>p;// 1 W. //scanf("%lld%lld%lld",&a,&b,&p);新聞熱點
疑難解答
