(POJ) 1201 -- Intervals [差分約束系統]

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

差分約束系統www。

考慮現在有很多不等式 x_i <= x_j + c ， 研究一下，會發現，這其實跟最短路徑的dis_i <= dis_j + w(i,j) 長得很像。

所以，遇到很多這種 x_i <= x_j + c的方程式，就可以使用最短路徑的建圖方法：連一條i到j的邊，邊權 = c。

那，這樣去跑最短路後，如果有遇到負環，那就代表無解。

那，如果有解的話，假設你是求從st開始求最短路徑到ed，那，dis_ed 就代表：在所有可行解中， x_ed - x_st 的最大值！

但是，這題要求的是最小的耶><。

可以先有一個小小的想法：我們可以去二分搜這個值，建一條x_st + min_dis <= x_ed 的邊。

會發現，如果是無解，那就是有負環！

那，在一點點觀察後，其實可以發現：要求x_ed - x_st  的最小值，其實就是 x_st - x_ed 的最大值，只是要取個負號XDD。

#include <iostream>
#include <cstdio>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int,int> pii;
const int N = 50006;
const int INF = (1<<27);

#define F first
#define S second

vector<pii> G[N];

void add_edge(int from,int to,int weight)
{
    G[from].push_back(make_pair(to,weight));
}

bool in_que[N];
int dis[N];

int spfa(int from,int to)
{
    queue<int> que;
    fill(dis,dis+N,INF);
    memset(in_que,0,sizeof(in_que));
    dis[from]=0;
    que.push(from);
    while (!que.empty())
    {
        int t=que.front();
        que.pop();
        in_que[t] = false;
        for (int i=0;G[t].size()>i;i++)
        {
            pii p=G[t][i];
            if (dis[p.F] > dis[t] + p.S)
            {
                dis[p.F] = dis[t] + p.S;
                if (!in_que[p.F])
                {
                    que.push(p.F);
                    in_que[p.F] = 1;
                }
            }
        }
    }
    return dis[to];
}

int main ()
{
    int n;
    while (scanf("%d",&n) != EOF)
    {
        int nn=N-3;
        for (int i=0;nn>=i;i++)
        {
            G[i].clear();
        }
        int ed = 0;;
        int st = N-3;
        for (int i=1;n>=i;i++)
        {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            ++x;
            ++y;
            --x;
            add_edge(y,x,-z);
            ed = max(ed,y+1);
            st = min(st,x);
            //add_edge(x,y,z);
        }
        for (int i=st+1;ed>=i;i++)
        {
            add_edge(i,i-1,0);
            add_edge(i-1,i,1);
        }
        printf("%d\n",-spfa(ed,st));
    }
}

(HDU) 5901. Count primes [pi函數，求一個數之前有多少質數]

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

這就超級玄學啦><。

直接附上連結。

code:

#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 = 320000 + 6;
const int C = 15005;
const int D = 506;

LL pi_form[N];
LL phi_form[C][D];
//LL p2_form[C][D];
LL p[N];
bool prime[N];

void init()
{
    MEM1(phi_form);
//    MEM1(p2_form);
    prime[0] = prime[1] = 1;
    int id=1;
    for (int i=2;N>i;i++)
    {
        if (!prime[i])
        {
            for (LL j=i*1LL*i;N>j;j+=i)
            {
                prime[j] = 1;
            }
            p[id++] = i;
        }
        pi_form[i] = pi_form[i-1] + (!prime[i]);
    }
}

LL pi(LL m);

LL p2(LL m,LL n)
{
    //cout<<"p2 = "<<p2_form[m][n]<<endl;
    //if (m<C && n<D && p2_form[m][n] != -1) return p2_form[m][n];
    //if (p[n] == 0) return 0;
    LL ret = 0;
    LL tmp=sqrt(m);
    for (LL i=n+1;p[i] <= tmp;i++)
    {
        ret += pi(m/p[i]) - pi(p[i]) + 1;
    }
    //if (m < C && n < D) p2_form[m][n] = ret;
    return ret;
}

LL phi2(LL m,LL n)
{
    if (m < C && n < D && phi_form[m][n] != -1) return phi_form[m][n];
    if (!n) return m;
    if (p[n] >= m) return 1;
    if (m<C && n<D) return phi_form[m][n] =  phi2(m,n-1) - phi2(m/p[n],n-1);
    return phi2(m,n-1) - phi2(m/p[n],n-1);
}

LL pi(LL m)
{
    //cout<<"pi = "<<m<<endl;
    if (m < N) return pi_form[m];
    else
    {
        LL n=ceil(cbrt(m));
        return phi2(m,n) + n - 1 - p2(m,n);
    }
}

int main () {
    //srand(time(NULL));
    init();
    LL n;
    while (scanf("%lld",&n) != EOF)
    {
        PL(pi(n));
    }
}

(POJ) 1811. Prime Test [Pollard Rho + Miller Rabin 算法]

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

Pollard Rho 跟 Miller Rabin 的合併算法

Miller Rabin 算法：用於快速檢查一個數字是不是質數

假設我們現在在檢查p。

若p是質數，根據費馬小定理，對於每個a，a ^ p === a (mod p)。

兩邊同除a (就自行想像一下吧XDD)，可能a ^ (p-1) === 1 (mod p)。

其中，若x ^ y === 1，x合理的解就只有可能是 +1 或 -1。

所以，可以發現，a ^ ( (p-1)/2 ), a ^ ( ( (p-1)/2 )/2 ), .......，只要是1 或 -1，那這個數字可能就是質數！

複雜度是好的 O(lg N)。

接下來介紹 Pollard Rho 算法，這個算法可以求出一個整數x的因數們。

在進入Pollard Rho算法之前，先用Miller Rabin判斷這個x是不是質數。

如果不是質數的話，我們先定義一個亂數生成函數f(x) = a*x^2 + c。

接著，選擇任意一個開始值s，並且令 f1 = f(s), f2 = f( f(s) )

之後，如果在某個時刻，f2和f1的差和x的最大公因數不是1 ， 那我們就找到一個因數了，遞迴下去求解。

如果在某個時候，f1跟f2一樣了，我們就在換一個起始點 & 生成函數的a跟c值。

要不然，執行f1 = f(f1), f2 = f(  f(f2) )，相當於是f1往前走一步，f2往前走兩步

數學家告訴我們，這樣做的話，複雜度大約只有O(N ^ (1/4))

#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);

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]);
    }
}

//#define
LL addd(LL a,LL b,LL mod)
{
    return ((a)+(b)>=(mod))?(a)+(b)-(mod):(a)+(b);
}

const int G = (1LL<<31)-1;

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

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

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

const bool PRIME = 1, COMPOSITE = 0;

bool miller_rabin(LL n,LL a)
{
    if (gcd(n,a) == n) return PRIME;
    else if (gcd(n,a) != 1) return COMPOSITE;
    LL d=n-1,r=0;
    while (d%2==0)
    {
        d >>= 1;
        ++r;
    }
    LL ret = ppow(a,d,n);
    if (ret == 1 || ret == n-1) return PRIME;
    while (r--)
    {
        ret = mull(ret,ret,n);
        if (ret == n-1) return PRIME;
    }
    return COMPOSITE;
}

bool isPrime(LL n)
{
    LL as[7] = {2,325,9375,28178,450775,9780504,1795265022};
    for (int i=0;7>i;++i)
    {
        //cout<<"i = "<<i<<endl;
        if (miller_rabin(n,as[i]) == COMPOSITE) return COMPOSITE;

    }
    return PRIME;
}

const LL C=2934852462451LL;
const LL D=126871905557494LL;
LL rnd=98134513458734897LL;

LL myRnd()
{
    return rnd = (rnd + C)^D;
}

LL a,c;

LL doo(LL x,LL n)
{
    return addd( mull( a, mull(x,x,n),n ),c ,n);
}

#define aabs(x) (x)>=0?(x):-(x)

LL solve(LL n)
{
    if (isPrime(n)) return n;
    if (!(n&1)) return 2;
    a=myRnd()%n;
    if (!a) a=1;
    c=myRnd()%n;
    //cout<<"a = "<<a<<" , c = "<<c<<endl;
    while (c == 0 || c==2) c=myRnd()%n;
    LL start = myRnd()%n;
    //cout<<"start = "<<start<<" , ";
    LL s1=doo(start,n);//cout<<"s1 = "<<s1<<endl;
    LL s2=doo(s1,n);
    //cout<<"n = "<<n<<" : ";
    while (true)
    {
        if (s1 == s2)
        {
            start = myRnd()%n;
            //a=myRnd()+1;
            a=myRnd()%n;
            if (!a) a=1;
            c=myRnd()%n;
            while (c == 0 || c==2) c=myRnd()%n;
            s1 = doo(start,n);
            s2 = doo(s1,n);
            continue;
        }
        //cout<<"s1 = "<<s1<<" , s2 = "<<s2<<endl;
        LL _=gcd(aabs(s1-s2),n);
        if (_ != 1)
        {
            return min(solve(_),solve(n/_));
        }
        s1 = doo(s1,n);
        s2 = doo(s2,n);
        s2 = doo(s2,n);
    }
}

int main () {
    //srand(time(NULL));
    int T;
    Si(T);
    while (T--)
    {
        LL n;
        SL(n);
        if (isPrime(n))
        {
            puts("Prime");
        }
        else
        {
            PL(solve(n));
        }
    }
}