scturtle's 渣代码集散地

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

不断读取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;
}

多重背包见 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]);
    }
}

Source Code

• 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();
      }
  }