程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> BZOJ2242 [SDOI2011]計算器 題解&代碼

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

編輯:關於C語言

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


題意:有三種要求:
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
        
   
						

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved