国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

Bzoj 2242: [SDOI2011]計算器(BSGS)

2019-11-11 07:08:03
字體:
來源:轉載
供稿:網友

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);
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 绍兴市| 射阳县| 澄江县| 常山县| 涡阳县| 方城县| 古蔺县| 陆河县| 镶黄旗| 云林县| 盘锦市| 西和县| 贵溪市| 内黄县| 彩票| 无为县| 崇礼县| 海盐县| 九江县| 罗山县| 乌拉特中旗| 米易县| 巴彦淖尔市| 深州市| 河间市| 静宁县| 庆城县| 新郑市| 莎车县| 陕西省| 鸡东县| 蕉岭县| 祥云县| 周至县| 息烽县| 乌鲁木齐市| 静宁县| 洛宁县| 蕲春县| 海林市| 阿尔山市|