Miller-Robbin 素数测试

2010年7月02日 18:13

如果一个数是伪素数,他几乎肯定是素数,如果一个数不是伪素数,他一定不是素数。

不断读取2~n-1的基b(s次),计算每次是否都有 exp(b,n-1)mod n == 1

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define maxn 100001
#define s 10
bool isprim[maxn];

void shai()
{
    for(int i=0;i<maxn;i++) isprim[i]=1;
    int t;
    for(int i=2;i<=maxn/2;i++)
    {
        t=i+i;
        while(t<maxn)
        {
            isprim[t]=0;
            t+=i;
        }
    }
}

int modexp(int a,int b,int m)
{
    __int64 ans=1;__int64 t=a%m;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*t)%m;
            b--;
        }
        t=(t*t)%m;
        b>>=1;
    }
    return ans;
}

bool MillerRobbin(int n)
{
    for(int i=1;i<=s;i++)
    {
        int a=rand()%(n-2)+2;
        if (modexp(a,n-1,n)!=1) return false;
    }
    return true;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    shai();
    for(int i=3;i<maxn;i++)
    {
        if(MillerRobbin(i)!=isprim[i])
            cout<<i<<endl;
    }
}

原来的这个是抄黑书上的,貌似只是用费马小定理来检验的,下面的这个应该才是正确的吧,正确率确实很高:

bool MillerRobbin(int n)
{
    if(n==2) return 1;
    else if((n&1)==0) return 0;
    int a,d;
    long long t;
    for(int i=0;i<s;i++)
    {
        a=rand()%(n-1)+1;
        d=n-1;
        while((d&1)==0) d>>=1;
        t=modexp(a,d,n);
        while(d!=n-1&&t!=1&&t!=n-1)
        {
            t=(t*t)% n;
            d<<=1;
        }
        if(t==n-1||(d&1)==1) continue;
        else return 0;
    }
    return 1;
}

评论(4) 阅读(2486)

poj 1014 多重背包

2010年6月17日 19:51

多重背包见 http://www.cgang.tk/pack/P03.html

mac下还是用macvim更顺手一些

在家,混混度日

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int v[7];
int sum,V;
int f[100000];

void CompletePack(int cost,int weight)
{
    for(int i=cost;i<=V;i++)
        f[i]=max(f[i],f[i-cost]+weight);
}

void ZeroOnePack(int cost,int weight)
{
    for(int i=V;i>=cost;i--)
        f[i]=max(f[i],f[i-cost]+weight);
}

void MultiplePack(int cost,int weight,int amount)
{
    if(cost*amount>=V)
    {
        CompletePack(cost,weight);
        return;
    }
    int k=1;
    while(k<amount)
    {
        ZeroOnePack(k*cost,k*weight);
        amount-=k;
        k*=2;
    }
    ZeroOnePack(amount*cost,amount*weight);
}


int main () 
{
    //freopen("in.txt","r",stdin);
    int cas=1;
    while(1)
    {
        sum=0;
        for(int i=1;i<=6;i++)
        {
            cin>>v[i];
            //v[i]=v[i]%60;
            sum+=i*v[i];
        }
        if(sum==0) break;
        cout<<"Collection #"<<cas++<<":"<<endl;

        if(sum%2)
        {
            cout<<"Can't be divided."<<endl<<endl;
            continue;
        }

        V=sum/2;
        memset(f,0,sizeof(f));
        for(int i=1;i<=6;i++)
        {
            MultiplePack(i,i,v[i]);
        }

        if(f[V]==V)
            cout<<"Can be divided."<<endl<<endl;
        else
            cout<<"Can't be divided."<<endl<<endl;
    }

}

14/10/10:背包又忘得差不多了...

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int V;
int f[100000];

void CompletePack(int cost,int weight)
{
    for(int i=cost;i<=V;i++)
        f[i]=max(f[i],f[i-cost]+weight);
}

void ZeroOnePack(int cost,int weight)
{
    for(int i=V;i>=cost;i--)
        f[i]=max(f[i],f[i-cost]+weight);
}

void MultiplePack(int cost,int weight,int amount)
{
    if(cost*amount>=V)
    {
        CompletePack(cost,weight);
        return;
    }
    int k=1;
    while(k<amount)
    {
        ZeroOnePack(k*cost,k*weight);
        amount-=k;
        k*=2;
    }
    ZeroOnePack(amount*cost,amount*weight);
}


int main ()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int cash,N,n[11],d[11];
    while(scanf("%d%d",&cash,&N)!=EOF)
    {
        for(int i=1;i<=N;i++)
            scanf("%d%d",&n[i],&d[i]);
        V=cash;
        memset(f,0,sizeof(f));
        for(int i=1;i<=N;i++)
            MultiplePack(d[i],d[i],n[i]);
        printf("%d\n",f[V]);
    }
}

评论(0) 阅读(2846)

poj 3126 第一个BFS题

2010年5月22日 07:44

Source Code

Problem: 3126   User: scturtle
Memory: 776K   Time: 16MS
Language: G++   Result: Accepted
  • Source Code
    #include <iostream>
    #include <cstring>
    #include <queue>
    using namespace std;
    #define MAX 9999
    int prime[MAX+1];
    int visit[MAX+1];
    int st,ed;
    int bas[4]= {1,10,100,1000};
    void shai()
    {
        for(int i=2; i<=MAX; ++i) prime[i]=1;
        int t;
        for(int i=2; i<=MAX/2; ++i)
        {
            t=2*i;
            while(t<=MAX)
            {
                prime[t]=0;
                t+=i;
            }
        }
    }
    
    void bfs()
    {
        fill(visit,visit+9999,0);
        queue<int> q;
        queue<int> qs;
        int t,ts;
        int n,ns;
        ts=0;
        t=st;
        q.push(t);visit[t]=1;
        qs.push(ts);
        int num,i,j;
        while(1)
        {
            t=q.front();q.pop();
            ts=qs.front();qs.pop();
            if(t==ed)
            {
                cout<<ts<<endl;
                return;
            }
            for(i=0; i<4; ++i)
                for(j=0; j<10; ++j)
                {
                    if(i==3&&j==0) continue;
                    num=t/bas[i]%10;
                    if(num!=j)
                    {
                        n=t-num*bas[i]+j*bas[i];
                        ns=ts+1;
                        if(!visit[n]&&prime[n]) {q.push(n);visit[n]=1;qs.push(ns);}
                    }
                }
        }
    
    }
    int main()
    {
        shai();
        int cas;
        cin>>cas;
        while(cas--)
        {
            cin>>st>>ed;
            bfs();
        }
    }
    

评论(0) 阅读(1957)