(POJ) 2417. Discrete Logging [baby step giant step, bsgs算法]

http://poj.org/problem?id=2417

題目可以簡化成求a ^ n === b (mod p)。

有一個想法是：把n拆成 x * m + y，y < m，在這裡取m = ceil( sqrt(n) )。

這時，我們就可以枚舉a ^ y，把這個表存在hash表裡面，接著枚舉a ^ x*m。

#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
#include <utility>
using namespace std;

int mull(int a,int b,int mod)
{
    return a*1LL*b%mod;
}

int ppow(int a,int n,int mod)
{
    int ret=1;
    int now=a;
    while (n)
    {
        if (n&1)
        {
            ret = mull(ret,now,mod);
        }
        now = mull(now,now,mod);
        n >>= 1;
    }
    return ret;
}

//hash table

const int C = 397184;

int get_pos(int x)
{
    return x%C;
}

int now_vis;

int vis_id[C];
map<int,int> mpp[C];

bool has_val(int pos,int ori_pos)
{
    if (vis_id[pos] == now_vis)
    {
        if (mpp[pos].find(ori_pos) != mpp[pos].end()) return true;
        else return false;
    }
    return false;
}

void set_val(int pos,int val,int ori_pos)
{
    if (vis_id[pos] != now_vis) mpp[pos].clear();
    vis_id[pos] = now_vis;
    mpp[pos][ori_pos] = val;
}

int get_val(int pos,int ori_pos)
{
    return mpp[pos][ori_pos];
}

void solve(int p,int b,int n)
{
    //b^L == n (mod p)
    //P < 2**31, 2 <= B < P, 1 <= N < p
    if (p%b==0)
    {
        puts("no solution");
        return;
    }
    if (n==1)
    {
        puts("0");
        return;
    }
    int x = ceil(sqrt(double(p)));
    int now_val = 1;
    for (int i=0;x>i;i++)
    {
        if (has_val(get_pos(now_val),now_val) == false)
        {
            set_val(get_pos(now_val),i,now_val);
            //mp[now_val] = i;
        }
        now_val = mull(now_val,b,p);
        if (now_val == n)
        {
            printf("%d\n",i+1);
            return;
        }
    }
    int now_val_rev = ppow(now_val,p-2,p);
    int tmp_now_val = now_val;
    int tmp_now_val_rev = now_val_rev;
    for (int i=1;x>i;i++)
    {
        int target_val = mull(n,now_val_rev,p);
        if (has_val(get_pos(target_val),target_val))
        {
            printf("%lld\n",get_val(get_pos(target_val),target_val) + i*1LL*x);
            return;
        }
        now_val = mull(now_val,tmp_now_val,p);
        now_val_rev = mull(now_val_rev,tmp_now_val_rev,p);
    }
    puts("no solution");
}

int main ()
{
    int p,b,n;
    while (scanf("%d %d %d",&p,&b,&n) != EOF)
    {
        now_vis++;
        solve(p,b,n);
    }
}

(POJ) 2409. Let it Bead [burnside lemma 燒邊定理]

http://poj.org/problem?id=2409

burnside lemma  的應用

答案 = (所有置換群答案一樣的數量)/(置換群的數量)

把上面那兩個東西填進去即可XDD

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long      LL;
typedef long double    ld;
typedef pair<int,int>  pii;
typedef pair<LL,LL>    pLL;
typedef vector<int>    vint;
typedef vector<LL>     vLL;
typedef vector<pii>    vpii;
typedef vector<pLL>    vpLL;

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL);
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL,(f)*1LL);

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

#define IOS ios::sync_with_stdio(0); cin.tie(0);

int myRnd() {
    return abs(  ((rand()<<15) ^ rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)^rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 2e5 + 6;

int a[N];

LL poww(LL a,LL n)
{
    LL ret=1;
    REP1(i,n) ret*=a;
    return ret;
}

LL gcd(LL a,LL b)
{
    if (b==0) return a;
    else return gcd(b,a%b);
}

int main () {
    srand(time(NULL));
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF)
    {
        if (!n && !m)return 0;
        LL ret = 0;
        REP0(i,m)
        {
            ret += poww(n,gcd(i,m));
        }
        if (m%2==0)
        {
            ret += (m/2)*poww(n,m/2+1);
            ret += (m/2)*poww(n,m/2);
        }
        else
        {
            ret += m*(poww(n,m/2+1));
        }
        //cout<<"ret = "<<ret<<endl;
        PL(ret/(2*m));
    }
}

(POJ) 2891. Strange Way to Express Integers [中國剩餘定理]

http://poj.org/problem?id=2891

進化(?) 版的中國剩餘定理

原題題意：給出k條 x === a (mod m)的式子，求出最小的答案。

因為這次的mod的數字不再是質數，就不能用公式解，所以要考慮一些其他的算法。

我們考慮解以下兩個聯立方程式，其中a1, m1, a2, m2 是已知的。

x1 === a1 (mod m1)
x2 === a2 (mid m2)

其中，我們可以把上面兩條式子改寫成

x1 - a1 = t1 * m1
x2 - a2 = t2 * m2

整理可得

a1 + t1 * m1 = a2 + t2 * m2

移項可得

t1 * m1 - t2 * m2 = a2 - a1

其中，m1, m2, a2, a1是已知的，上面那個式子就相當於求ax + by = c(其中a,b,c已知) 的一組合法整數解，就可以用extgcd(拓展歐基里德算法)來求解

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long LL;

LL extgcd(LL a,LL b,LL &x,LL &y)
{
    if (b==0)
    {
        x=1;
        y=0;
        return a;
    }
    else
    {
        LL d=extgcd(b,a%b,y,x);
        y -= (a/b)*x;
        return d;
    }
}

LL mull(LL a,LL b,LL mod)
{
    a %= mod;
    b %= mod;
    LL ret=0;
    LL now=a;
    while (b)
    {
        if (b&1)
        {
            ret += now;
            ret %= mod;
        }
        now += now;
        now %= mod;
        b >>= 1;
    }
    return ret;
}

int main ()
{
    int n;
    while (scanf("%d",&n) != EOF)
    {
        vector<LL> a,m;
        for (int i=0;n>i;i++)
        {
            LL x,y;
            scanf("%lld %lld",&x,&y);
            a.push_back(y);
            m.push_back(x);
        }
        bool has_answer = true;
        LL nowa=0,nowm=0;
        for (int i=0;n>i;i++)
        {
            if (!i)
            {
                nowa = a[i];
                nowm = m[i];
                continue;
            }
            LL a1 = nowa, m1 = nowm;
            LL a2 = a[i], m2 = m[i];
            if (a1 > a2)
            {
                swap(a1,a2);
                swap(m1,m2);
            }
            LL t1,t2;
            LL gcd = extgcd(m1,m2,t1,t2);
            if ((a2-a1)%gcd != 0)
            {
                has_answer = false;
                break;
            }
            LL val = (a2-a1)/gcd;
            nowm = m1/gcd*m2;
            nowa = a1 + mull( mull(t1+nowm,val,nowm),m1,nowm );
            nowa %= nowm;
        }
        if (has_answer)
        {
            printf("%lld\n",nowa);
        }
        else
        {
            puts("-1");
        }
    }
}

(HDU) 5391. Zball in Tina Town [威爾森定理]

http://acm.hdu.edu.cn/showproblem.php?pid=5391

n很小的時候，直接乘 (不想管corner case XD)

簡單來講，就是要求 (n-1)! % n

若n是質數，根據 威爾森定理 ，答案就是n-1。

威爾森定理：若n是質數，則 (n-1)! === -1 (mod n)

否則，答案 = 0.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long      LL;
typedef long double    ld;
typedef pair<int,int>  pii;
typedef pair<LL,LL>    pLL;
typedef vector<int>    vint;
typedef vector<LL>     vLL;
typedef vector<pii>    vpii;
typedef vector<pLL>    vpLL;

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL);
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL,(f)*1LL);

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

#define IOS ios::sync_with_stdio(0); cin.tie(0);

int myRnd() {
    return abs(  ((rand()<<15) ^ rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)^rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 2e5 + 6;

int a[N];

bool prime(int x)
{
    for (int y=2;y*y<=x;y++)
    {
        if (x%y==0)return false;
    }
    return true;
}

int main () {
    srand(time(NULL));
    int T;
    Si(T);
    while(T--)
    {
        int n;
        Si(n);
        if (prime(n)) Pi(n-1)
        else if (n == 4) Pi(2)
        else Pi(0);
    }
}