程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> BZOJ2242 [SDOI2011]計算器題解&代碼

BZOJ2242 [SDOI2011]計算器題解&代碼

編輯：關於C

題意：有三種要求：
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)的最小非負整數。
分別處理即可

思路：
1顯然是快速冪了，純模板
2是擴展歐幾裡得（exgcd），求滿足xy-pk=z的最小x（k任意）
3利用了費馬小定理的性質a^(p-1)≡1(mod p),然後分塊降復雜度（太麻煩懶得寫直接抄黃學長代碼…捂臉）

/**************************************************************
    Problem: 2242
    User: Rainbow6174
    Language: C++
    Result: Accepted
    Time:2028 ms
    Memory:3272 kb
****************************************************************/

#include
#include
#include
#include
#define LL long long
using namespace std;
int T,k;
map vis;
LL y,z,x,a,b,m,t,mod,temp,flag;
LL pow(LL base,LL x)
{
    LL ret = 1;
    base %= mod;
    while(x)
    {
        if(x & 1)ret *= base,ret %= mod;
        base *= base;
        base %= mod;
        x >>= 1;
    }
    return ret;
}
LL gcd(LL x,LL y)
{
    if(!y)return x;
    return gcd(y,x%y);
}
LL exgcd(LL x,LL y)
{
    if(!y)
    {
        a=1,b=0;
        return x;
    }
    int ret=exgcd(y,x%y);
    //cout


						   
							
						
						
						
							上一頁:BZOJ2243 [SDOI2011]染色 題解&代碼
下一頁:BZOJ2241 [SDOI2011]打地鼠 題解&amp;代碼


				
					
						關於C
						
					
					
						
						
							
							C語言中的函數
							一、認清函數的真相
１、函數的由來
程序　 = 　數據 　&			
						
						
						
							
							C讀寫配置文件
							在項目開發中，經常需要讀取應用配置文件的初始化參數，在應用啟			
						
						
						
							
							數據結構之
							學過數據結構的都知道樹，那麼什麼是樹？ 樹（tre			
						
						
						
							
							一起talk C栗子吧（第一百六十回：C語言實例
							各位看官們，大家好，上一回中咱們說的是套接字通信模型的例子，			
						
						
						
							
							詳解結構體、類等內存字節對齊
								 先說個題外話：早些年我學C程序設計時，寫過一段			
						
						
						
							
							C語言終極面試寶典
							第一部分：基本概念及其它問答題 31、關鍵字static的作

BZOJ2242 [SDOI2011]計算器 題解&amp;代碼

BZOJ2242 [SDOI2011]計算器題解&代碼